【1错1对0】Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/

日期	是否一次通过	comment
2019-01-21 01:06	否	思路太僵
2019-01-21 01:06	Y

image.png

（来源：https://leetcode.com/problems/sum-of-left-leaves/）

关键：preOrder + 识别出left leaf node

1. 非递归：TODO；
2. 递归：preOrder，处理好何时加上()

1. 非递归

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        Stack<TreeNode> nodeS = new Stack<>();
        nodeS.push(root);
        
        int leftSum = 0;
        while(!nodeS.isEmpty()) {
            TreeNode node = nodeS.pop();
            if(node.left != null) {
                if(node.left.left == null && node.left.right == null) {
                    leftSum +=  node.left.val;
                }
            }
            if(node.right != null) {
                nodeS.push(node.right);
            }
            if(node.left != null) {
                nodeS.push(node.left);
            }
        }
        
        return leftSum;
    }
}

2.递归

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        
        TreeNode nodeSum = new TreeNode(0);
        helper(root, nodeSum);
        
        return nodeSum.val;
    }
    
    private void helper(TreeNode root, TreeNode nodeSum) {
        if(root == null) {
            return;
        }
        
        if(root.left != null) {
            if(root.left.left == null && root.left.right == null) {
                nodeSum.val += root.left.val;
            }
        }
        
        helper(root.left,nodeSum );
        helper(root.right,nodeSum );
    }
}