LeetCode:404. 左叶子之和

计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

方法一：

思想：把所有节点都当作根节点。递归处理

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
       public int sumOfLeftLeaves(TreeNode root) {
      if (root == null) {
            return 0;
        }
        Stack<TreeNode> rightStack = new Stack<>();
        int sum = 0;
        do {
            TreeNode left = root.left;
            TreeNode right = root.right;
            if (right != null) {
                rightStack.add(right);
            }
            if (left != null) {
                sum += getLeftValue(left, rightStack);
            }
            root = rightStack.empty() ? null : rightStack.pop();
        } while (root != null);
        return sum;
    }

 private  int getLeftValue(TreeNode root, Stack<TreeNode> rightStack) {
    if (root.right != null) {
      rightStack.add(root.right);
    }
    if (root.left != null) {
      return getLeftValue(root.left, rightStack);
    }

    return root.right == null ? root.val : 0;
  }

方法二

参考更简单的递归方法

  public static int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    return getValue(root.left, true) + getValue(root.right, false);

  }

  private static int getValue(TreeNode node, boolean isLeft) {
    if (node == null) return 0;
    // 叶子节点
    if (node.left == null && node.right == null) return isLeft ? node.val : 0;

    return getValue(node.left, true) + getValue(node.right, false);

  }