SumOfLeftLeaves [source code]

public class SumOfLeftLeaves {
    public int sumOfLeftLeaves(TreeNode root) {
        return go(root, false);
    }

    public int go(TreeNode root, boolean isLeft) {
        if (root == null) return 0;
        else if (isLeft && root.left == null && root.right == null) return root.val;
        else return go(root.left, true) + go(root.right, false);
    }
}

这个是我一开始写的版本; 这个版本是错的, 是因为这个 sum 的其实不是left leaves, 而是left children.

public int sumOfLeftLeaves(TreeNode root) {  
    return go(root, false);  
}  

public int go(TreeNode root, boolean isLeft) {  
    if (root == null) return 0;  
    int leftSum = go(root.left, true);  
    int rightSum = go(root.right, false);  
    return leftSum + rightSum + (isLeft ? root.val : 0);  
}

这里leftSum and rightSum两个 temp 可以直接 inline 到 return 里面去, 不过我还是保留了, 让你警惕premature refactoring;

尽管sum left children并不对, 但是我这里还是认为应该让每一个 node 都知道自己是不是一个left child. 这样到一个 leave 的时候才知道这个 leaf 是不是left leaf.

这个is left child的信息就用一个 flag 来传递, 这样每一个 root 都知道自己是不是 left. 为什么要作为参数传递? 因为是否是 left 这个决定应该是交给每一个 parent 来做的决定, 这种决定一般很正常的做法就是要么是在 body 的代码里面本身就有一定的 conditional 处理, 要么就是把这个状态作为参数传递下去;

至于算法在 recursion 层面上的设计, 思考方式就是思考how to make the decision for this node(level), based on what node it is. 比如, 这里你应该考虑:

1. if root is internal (neither left or right is null): then return resLeft and resRight;
2. if root is right leaf: return 0;
3. if root is left leaf: return root.val;

速度是9ms, 50%, 差强人意;

好像看他们写算法的人, 在处理 tree 问题的时候另外一种思路就是不强调recursion 角度的理解, 而是单纯强调 DFS 层面的理解. 也就是在他们看来, 你的一个DFS 代码代表的其实就是一个iterator, 类似于你 iterate 一个 array 是一样的意思; 你要做的, 其实就是在这个 iteration 的过程中找到合适的 conditional 点, 做出合适的举动;

用这个思路判断 leaf 肯定要容易很多, 不过怎么判断 left?

这个就是他们的做法: 这个是 submission 最优解, 实际上的速度跟我的是差不多的, 就是波动导致的差别:

public class Solution {  
    public int sumOfLeftLeaves(TreeNode root) {  
        if (root == null) {  
            return 0;  
        }  
        int output = 0;  
        if (root.left != null) {  
            if (root.left.left == null && root.left.right == null) {  
                output = output + root.left.val;  
            } else {  
                output = output + sumOfLeftLeaves(root.left);  
            }  
        }  
        output = output + sumOfLeftLeaves(root.right);  
        return output;  
    }  
}

这个思路其实比较取巧, 而且其实我也基本想到了, 就是没有落实: 他们这个算法判断的不是left child, 也不是left leaf, 而是parent of left leaf. 这个是很好判断的, 虽然我当时没有想到, 因为我没有想到用root.left.left这样的用法: 这种全 public 的 API 还是有点不太习惯;

绕过这个弯, 用 DFS 的思路就很好解了, 只要在 DFS order 的路上挨个判断是否是immediate parent to a left leaf就行了;

这个是 discussion 上面别人写的 BFS 代码:

public class Solution {  
    public int sumOfLeftLeaves(TreeNode root) {  
        if(root == null || root.left == null && root.right == null) return 0;  

        int res = 0;  
        Queue<TreeNode> queue = new LinkedList<>();  
        queue.offer(root);  

        while(!queue.isEmpty()) {  
            TreeNode curr = queue.poll();  

            if(curr.left != null && curr.left.left == null && curr.left.right == null) res += curr.left.val;  
            if(curr.left != null) queue.offer(curr.left);  
            if(curr.right != null) queue.offer(curr.right);  
        }  
        return res;  
    }  
}

虽然在这一题来说, BFS 并没有什么特别的优势;

这个是 DFS:

Iterative method. Here for each node in the tree we check whether its left child is a leaf. If it is true, we add its value to answer, otherwise add left child to the stack to process it later. For right child we add it to stack only if it is not a leaf.

public int sumOfLeftLeaves(TreeNode root) {  
    if(root == null) return 0;  
    int ans = 0;  
    Stack<TreeNode> stack = new Stack<TreeNode>();  
    stack.push(root);  

    while(!stack.empty()) {  
        TreeNode node = stack.pop();  
        if(node.left != null) {  
            if (node.left.left == null && node.left.right == null)  
                ans += node.left.val;  
            else  
                stack.push(node.left);  
        }  
        if(node.right != null) {  
            if (node.right.left != null || node.right.right != null)  
                stack.push(node.right);  
        }  
    }  
    return ans;  
}

这两个代码虽然对于这一题的个性没有什么特别的优势, 但是对于帮助学习 iterative 代码还是很有意义的. 用 iterative 写的时候, 核心是stack or queue这两个核心结构, 然后每一个 iteration 的核心操作, 相对于普通的 recursive, 我们还要多考虑怎么更新这些核心结构;

不过 iterative 有一个好处就是自动有类似于 global 一样的东西可以用了(因为直接就是 temp var);

Problem Description

Find the sum of all left leaves in a given binary tree.

Example:

3  

/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
Difficulty:Easy
Category:Algorithms
Acceptance:46.85%
Contributor: LeetCode
Companines
Facebook
Related Topics
tree