BM26 求二叉树的层序遍历

思想：创建二维数组进行存储每层的内容，直接判断二维数组的size就是其中有多少个一维数组，要让一维数组个数大于层高，相等时则上层已遍历完成，每层的内容对应二维数组中一维数组的内容。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
private:
    vector<vector<int>> result;
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        if(root==NULL){
            return result;
        }
        fun(0,root);
        return result;
    }
    void fun(int l,TreeNode* root){
        if(result.size()==l){
            vector<int> blank;
            result.push_back(blank);
        }
        result[l].push_back(root->val);
        if(root->left!=NULL){
            fun(l+1, root->left);
        }
        if(root->right!=NULL){
            fun(l+1, root->right);
        }
    }
};

BM27 按之字型顺序打印二叉树

思路：与层序遍历一致，输出结果时，奇数行进行翻转。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    vector<vector<int>> result;
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        if(pRoot==NULL){
            return result;
        }
        fun(0,pRoot);
        for(int i=0;i<result.size();i++){
            if(i%2==1){
                reverse(result[i].begin(),result[i].end());
            }
        }
        return result;
    }
    void fun(int l,TreeNode* pRoot){
        if(result.size()==l){
            vector<int> blank;
            result.push_back(blank);
        }
        result[l].push_back(pRoot->val);
            if(pRoot->left!=NULL){
                fun(l+1, pRoot->left);
            }
            if(pRoot->right!=NULL){
                fun(l+1,pRoot->right);
            }
    }
};

BM28 二叉树的最大深度

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
private:
    int maxdep=0;
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if(root==NULL){
            return maxdep;
        }
        fun(1, root);
        return maxdep;
    }
    void fun(int l,TreeNode* root){
        if(l>maxdep){
            maxdep=l;
        }
        if(root->left!=NULL){
            fun(l+1, root->left);
        }
        if(root->right!=NULL){
            fun(l+1,root->right);
        }
    }
};

BM29 二叉树中和为某一值的路径（一）

思路：

每次减去sum，当到叶子结点时，判断是否sum为0，为0则为true，不为0返回false，分别遍历左右子树，当任意一个子树满足时，即返回true

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(root==NULL) return false;
        sum-=root->val;
        if(root->left==nullptr&&root->right==nullptr){
            if(sum==0) return true;
            else return false;
        }
        return hasPathSum(root->left,sum)||hasPathSum(root->right,sum);
    }
};

BM30 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

思路：将二叉树遍历放入数组中之后，将数组排序，再将排序好的数组整理为双向链表；

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
private:
    vector<int> a;
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree==NULL){
            return NULL;
        }
        PreOrder(pRootOfTree);
        sort(a.begin(),a.end());
        TreeNode* b=new TreeNode(a[0]);
        TreeNode* s=b;
        for(int i=1;i<a.size();i++){
            TreeNode* t=new TreeNode(a[i]);
            t->left=s;
            s->right=t;
            s=t;
        }
        a.clear();
        return b;
    }
    void PreOrder(TreeNode* pRootOfTree){
        a.push_back(pRootOfTree->val);
        if(pRootOfTree->left!=NULL)
            PreOrder(pRootOfTree->left);
        if(pRootOfTree->right!=NULL)
            PreOrder(pRootOfTree->right);
    }
};

BM31 对称的二叉树

递归解法：从底到顶，判定是否满足对称要求

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==NULL) return true;
        return fun(pRoot->left,pRoot->right);
    }
    bool fun(TreeNode* left,TreeNode* right){
        if((!left && right)||(left&&!right))
            return false;
        if(!left&&!right)
            return true;
        if(left->val!=right->val)
            return false;
        return fun(left->left,right->right)&&fun(left->right,right->left);
    }
};