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

发布时间:2023年12月27日

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

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;
    }
};
文章来源:https://blog.csdn.net/2303_77739929/article/details/135248567
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。