Day21 404左叶子之和 513找树左下角的值

? ? ? ? 首先要明白如何判断出一个结点是不是左叶子，要从父节点来判断，如果这个父节点的左孩子不为空，左孩子的左孩子和左孩子的有孩子都为空，就说明他的左孩子是左叶子了。如果用递归法，主要是单层递归逻辑那里需要多加考虑，本题利用后序的方法比较好，左右中，首先往左进行遍历，判断一下是否是左叶子，之后右递归遍历，最后中间节点（父节点）加和。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right== NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右

        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};

? ? ? ? 本代码可以进行精简，其实也比较好理解：????????

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int leftValue = 0;
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
            leftValue = root->left->val;
        }
        return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

? ? ? ? ?当然，本题也可以采用迭代法，这里我采用比较熟悉的层序：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr) que.push(root);
        int sum = 0;
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left && !node->left->left && !node->left->right){
                    sum += node->left->val;
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return sum;
    }
};

? ? ? ? ? ? ? ? 平时我们解二叉树的题目时，已经习惯了通过结点的左右孩子判断本节点的属性，二本题我们要通过结点的父节点判断本节点的属性，属于是拓宽了思路。

513 找树左下角的值

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

首先想到的一定是迭代遍历里的层序，和之前那道找最右边结点很像。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

? ? ? ? ?但是本题最好还是要再训练一下递归法：如果一直向左遍历到最后一个，不一定是最终的答案，因为他未必是最后一行。那么如何判断是最后一行呢，其实就是深度最大的叶子节点。既然要找到最左边，那么只要保证优先左边搜索，记录深度最大的叶子节点即可。

? ? ? ? 定义两个全局变量，maxdepth记录最大深度，result记录最大深度最左节点的数值。当遇到叶子结点的时候，就需要统计一下最大深度了，同时，本题还需要使用回溯，如果不回溯的话，高度就会一直递增错误。

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

? ? ? ? 当然回溯过程也可以简化，和上次的回溯简化其实类似：

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            traversal(root->left, depth + 1); // 隐藏着回溯
        }
        if (root->right) {
            traversal(root->right, depth + 1); // 隐藏着回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};