二叉树递归

113 路径总和 II

class Solution {
public:
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> tmp;
        if(!root) return res;
        
        if(root->val==sum && !root->left && !root->right){
            tmp.push_back(root->val);
            res.push_back(tmp);
            return res;
        }
        
        vector<vector<int>> lefts = pathSum(root->left,sum-root->val);
        for(int i =0;i<lefts.size();i++){
        // 把父节点 追加到vector<> 的前面，
            lefts[i].insert(lefts[i].begin(),root->val);
            res.push_back(lefts[i]);
        }
        
        vector<vector<int>> rights = pathSum(root->right,sum-root->val);
        for(int i =0;i<rights.size();i++){
            rights[i].insert(rights[i].begin(),root->val);
            res.push_back(rights[i]);
        }
        
        return res;
    }
    
};


// 解法2 深度递归遍历

    void dfs(TreeNode* root, int sum,vector<int>& tmp,vector<vector<int>>& res){
        if(!root) return ;
        
        tmp.push_back(root->val);
        if(sum==root->val && !root->left && !root->right){
            res.push_back(tmp);
        }
        
        dfs(root->left,sum-root->val,tmp,res);
        dfs(root->right,sum-root->val,tmp,res);
        tmp.pop_back();
           
    }
    
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> tmp;
        if(!root) return res;
        dfs(root,sum,tmp,res);
        return res;
    }

129. 求根到叶子节点数字之和

class Solution {
public:
    void dfs(TreeNode* root,int cnt,vector<int>& tmp){
        if(!root) return ;
        if(!root->left && !root->right){
            tmp.push_back(cnt*10+root->val);
        }
        dfs(root->left,cnt*10+root->val,tmp);
        dfs(root->right,cnt*10+root->val,tmp);
    }
    
    
    int sumNumbers(TreeNode* root) {
       int res = 0;
        if(!root) return res;
        vector<int> tmp;
        dfs(root,0,tmp);
        
        for(auto i:tmp)
            res+=i;
        
        return res;
    }
};

124. 二叉树中的最大路径和

class Solution {
public:
   int res;
   int pathSum(TreeNode* root){
    if(!root) return 0;
    int left = max(pathSum(root->left),0);
    int right = max(pathSum(root->right),0);
    res = max(res,root->val+left+right);
    return root->val+max(0,max(left,right));
    }


int maxPathSum(TreeNode* root) {
    if(!root) return 0;
    res = root->val;
    pathSum(root);
    return res;
    }
};

404- 左叶子之和(easy)

//// 计算给定二叉树的所有左叶子之和。
   3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

 void dfs(TreeNode* root,int& sum,bool flag){
        if(!root) return ;
        if(flag && !root->left && !root->right)
            sum+=root->val;
        dfs(root->left,sum,true);
        dfs(root->right,sum,false);
    }
    
    
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if(!root) return 0;
        dfs(root,sum,false);
        return sum;
    }

// 解法2

int res = 0;
int sumOfLeftLeaves(TreeNode* root) {
    int sum = 0;
    if(!root) return 0;
    
    if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
        res += root->left->val;
    sumOfLeftLeaves(root->left);
    sumOfLeftLeaves(root->right);
    return  res;
}

// 解法3 return 理解
// res累加，是给首次调用函数return用的，如果
int sumOfLeftLeaves(TreeNode* root) {
  if(root == null) return 0;
  int res = 0;
  //判断节点是否是左叶子节点，如果是则将它的和累计起来
  if(root.left != null && root.left.left == null && root.left.right == null){
      res += root.left.val;
  }
  return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + res;
}

513. 找树左下角的值()

给定一个二叉树，在树的最后一行找到最左边的值。

注意：是树最后一行最左边的值，不是最后一行最左子树的值
可以使用层次遍历，取每一层第一个元素，然后深度每加一层，更新一次最左的元素

    int findBottomLeftValue(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> pq;
        pq.push(root);
        TreeNode* res;
        
        while(!pq.empty()){
            int len = pq.size();
            for(int i=0;i<len;i++){
                TreeNode* node = pq.front();
                pq.pop();
                
                if(i==0) res = node;
                if(node->left)
                    pq.push(node->left);
                if(node->right)
                    pq.push(node->right);   
            }  
        }
        return res->val;
    }