7.16 Tree Recursion

to do

注意以下path的定义是什么？

1] Minimum Depth of Binary Tree

    int minDepth(TreeNode* root) {
       if (!root) return 0;

       queue<TreeNode*> q;
       q.push(root);
       q.push(nullptr);
       int ct = 0;
       
       while (!q.empty()) {
           TreeNode* curr=q.front();
           q.pop();
           if (!curr) {
               if (q.empty()) break;
               else q.push(curr);
               ++ct;
           } else {
               if (!curr->left && !curr->right) break;
               if (curr->left)  q.push(curr->left);
               if (curr->right) q.push(curr->right);
           }
       }
       
       return ct+1;
    }

2] Path Sum

其实不用记sum until then; 有负数

    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) return sum==root->val;
        
        return hasPathSum(root->left, sum-root->val) 
            || hasPathSum(root->right, sum-root->val);
    }

6] Sum Root to Leaf Numbers

又没看题。。

    void dfs(TreeNode* root, int path, int& sum){
        if (!root) return;
        path = path*10 + root->val;
        
        if (!root->left && !root->right) {
            sum += path;
            return;
        }
        dfs(root->left, path, sum);
        dfs(root->right, path, sum);
    }
    
    int sumNumbers(TreeNode* root) {
        int sum=0;
        dfs(root, 0, sum);
        return sum;
    }