一. 树的总结

• 树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；

1.1 常见的 DFS ： 先序遍历、中序遍历、后序遍历；

• DFS遍历：

class TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

 void traverse(TreeNode root){
    //前序遍历
    traverse(root.left)
    //中序遍历
    traverse(root.right)
    //后序遍历
}    

1.2 常见的 BFS ： 层序遍历（即按层遍历）。

• 使用队列实现。

二. Easy 题目

2.1 剑指 Offer 55 - I. 二叉树的深度

方法一：递归-深度优先-后序遍历

• 递归重点：树的深度等于 max(左子树的深度和右子树的深度) + 1.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root? max(maxDepth(root->left), maxDepth(root->right))+1 : 0;
    }
};

方法二：层序遍历-队列

• depth的起始值。

class Solution {
public:
    int maxDepth(TreeNode* root) {
      if(!root) return 0;
      queue<TreeNode*> q;
      q.push(root);
      int depth=0;
      while(q.size()>0){
          int n=q.size();
          for(int i=0;i<n;i++){
              TreeNode* temp=q.front();
              q.pop();
              if(temp->left) q.push(temp->left);
              if(temp->right) q.push(temp->right);
          }
          depth++;
      }
      return depth;
    }
};

2.2 剑指 Offer 27. 二叉树的镜像

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root ==NULL)
        {return root;}

        swap(root);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }

    void swap(TreeNode* node){
        TreeNode* tmp=node->left;
        node->left=node->right;
        node->right=tmp;
    }
};

2.3 剑指 Offer 54. 二叉搜索树的第k大节点

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        if(root ==NULL) return NULL;
        int tree_num = TreeNum(root->right)+1;
        if(tree_num == k) return root->val;
        else if(tree_num < k ) return kthLargest(root->left,k-tree_num);
        else return kthLargest(root->right,k);
    }

    int TreeNum(TreeNode* root){
        if (root ==NULL) return 0;
        return 1+TreeNum(root->left)+TreeNum(root->right);
    }
};

• 树的中序遍历

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        if(root ==NULL) return -1;
        vector<int> num;
        dfs(num,k,root);
        return num[k-1];
    }

    void dfs(vector<int> &num, int &k, TreeNode* root){
        if (root==NULL) return;
        dfs(num,k, root->right);
        if(num.size()==k) return;
        num.push_back(root->val);
        dfs(num,k, root->left);
    }
};

2.5 剑指 Offer 32 - II. 从上到下打印二叉树 II

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL) return result;

        queue<TreeNode*> my_queue;
        my_queue.push(root);

        while(!my_queue.empty()){
            int depth=my_queue.size();
            vector<int> tmp;
            for(;depth>0;depth--){
                TreeNode* top_node = my_queue.front();
                my_queue.pop();
                if(top_node->left) 
                   my_queue.push(top_node->left);

                if(top_node->right)
                    my_queue.push(top_node->right);
                tmp.push_back(top_node->val);
            }
            result.push_back(tmp);
        }
        return result;
    }
};

2.6 剑指 Offer 55 - II. 平衡二叉树

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return getDepth(root) != -1;
    }

    int getDepth(TreeNode* root){
        if (root == NULL) return 0;
        int left_depth = getDepth(root->left);
        if(left_depth ==-1) return -1;
        int right_depth = getDepth(root->right);
        if(right_depth ==-1) return -1;
        return abs(left_depth-right_depth) >1? -1:max(left_depth,right_depth)+1;
    }
};

三. Medium题目

3.1 剑指 Offer 07. 重建二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() <=0 || inorder.size()<=0 )
            return NULL;
        
        return ConstructCore(0,preorder.size()-1, 0, preorder.size()-1, preorder, inorder);
    }

    TreeNode* ConstructCore(int preorder_start,int preorder_end, int inorder_start,int inorder_end, vector<int>& preorder, vector<int>& inorder){
        int root_value=preorder[preorder_start];
        TreeNode* root=new TreeNode(root_value);
        if(preorder_start == preorder_end){
            if(inorder_start == inorder_end && preorder[preorder_start]==inorder[inorder_start])
               return root;
        }

        int root_inorder=0;
        while(root_inorder<inorder_end && inorder[root_inorder] != root_value){
            ++root_inorder;
        }

        int left_length=root_inorder-inorder_start;
        if(left_length>0)
            root->left=ConstructCore(preorder_start+1,preorder_start+left_length,inorder_start, root_inorder-1, preorder, inorder);
        if(left_length < preorder_end-preorder_start)
            root->right=ConstructCore(preorder_start+left_length+1,preorder_end, root_inorder+1, inorder_end, preorder, inorder);
        return root;
    }
};

3.2 剑指 Offer 34. 二叉树中和为某一值的路径

• 注意：很多判断条件，中间值，用减法消耗更少，避免保存中间变量。

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        vector<int> one_path;
        findPath(root, result, one_path, sum);
        return result;
    }

    void findPath(TreeNode* root, vector<vector<int>>& path,vector<int> &one_path, int sum){
      if (root ==NULL) return;
      one_path.push_back(root->val);
      sum -=root->val;
      if( sum == 0 && root->left == NULL && root->right == NULL){           
        path.push_back(one_path);
      }
      if(root->left != NULL)
        findPath(root->left, path, one_path, sum);
      if(root->right != NULL)
        findPath(root->right, path, one_path, sum); 
      one_path.pop_back();       
    }
};

• 可以声明成类的成员

class Solution {
private:
    vector<vector<int>> path;
    vector<int> one_path;

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        findPath(root, sum);
        return path;
    }

    void findPath(TreeNode* root, int sum){
      if (root ==NULL) return;
      one_path.push_back(root->val);
      sum -=root->val;
      if( sum == 0 && root->left == NULL && root->right == NULL){           
        path.push_back(one_path);
      }
        if(root->left != NULL)
            findPath(root->left, sum);
        if(root->right != NULL)
            findPath(root->right, sum); 
        one_path.pop_back();       
    }
};

3.3 剑指 Offer 26. 树的子结构

• 递归逻辑拆分合理

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
       if(A== NULL|| B==NULL) return false;
       return judgeSame(A,B) || isSubStructure(A->left,B)||isSubStructure(A->right,B); 
    }

    bool judgeSame(TreeNode* A, TreeNode* B){
        if(B==NULL )
            return true;
        if(A== NULL|| A->val != B->val) return false;
        return judgeSame(A->left, B->left) && judgeSame(A->right, B->right);
    }
};