LeetCode 404：左叶子之和

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 164

LeetCode 404

题目：

思路：

当前节点是无法判断左叶子节点的，要使用父节点来判断左子节点是不是左叶子！

使用后序遍历。

递归三部曲：

参数为根节点，返回值为数值之和，所以为int
确定终止条件
依然是 if (root == NULL) return 0;
确定单层递归的逻辑
当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。
判断左叶子的条件：root.left!=null && root.left.left==null && root.left.right==null

用left和right接住子树递归的结果，是递归整棵树
是回溯思想。

Java实现：递归回溯


class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // 和子树有关，后序遍历
        if(root==null){
            return 0;
        }
        // 有值递归
        int left=sumOfLeftLeaves(root.left);
        int right=sumOfLeftLeaves(root.right);

        // 后序遍历
        int r=0; // 当前节点的左叶子节点的值
        if(root.left!=null && root.left.left==null && root.left.right==null){ // 判断是否为左叶子
            r=root.left.val;
        }
        int sum=left+right+r;
        return sum;
    }
}

或者：设置实例变量sum，void后序遍历


class Solution {
    int sum=0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        check(root);
        return sum;
    }

    void check(TreeNode root){
        if(root==null){
            return ;
        }
        //后序 回溯
        check(root.left);
        check(root.right);
        
        //判断左叶子  // 防止空指针异常
        if(root.left!=null && root.left.left==null && root.left.right==null ){
            sum=sum+root.left.val;
        }
    }
}