404左叶子之和

题目描述

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

思路分析

递归终止的条件是什么？一次递归中要进行什么操作？递归想要返回什么信息？

基于前序递归模板。

终止条件：节点为空

递归中操作：为左叶节点时，将节点值计入sum

• 可以用基础的前序模板，定义全局变量sum；
• 也可以将前序模板返回值改成int，则递归想要返回信息就是 左右子树的左叶节点和 + 当前左叶节点和。

代码实现

    private int sum = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        process(root,false);
        return sum;
    }

    public void process(TreeNode root, boolean flag) {
        if (root == null) {
            return;
        }
        if (flag && root.left == null && root.right == null) {
                sum += root.val;
        }
        process(root.left, true);
        process(root.right,false);
    }
    
    public static int process(TreeNode root, boolean flag) {
        if (root == null) {
            return 0;
        }
        int leave = 0;
        if (flag && root.left == null && root.right == null) {
            leave += root.val;
        }
        return process(root.left, true) + leave +
                process(root.right, false);
    }