📃 题目描述

题目链接：404. 左叶子之和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

示例：

    3
   / \
  9  20
    /  \
   15   7

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

🔔 解题思路

递归

这题简单，直接遍历一遍二叉树，当遇到左叶子节点时，就记录下，以前序遍历为例：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // 递归出口
        if (root == null) {
            return 0;
        }

        int leftLeafVal = 0;

        // 根节点的左叶子节点
        if (root.left != null && root.left.left == null && root.left.right == null) {
            leftLeafVal = root.left.val;
        }
        // 递归处理左右子树的左叶子节点
        int leftSum = sumOfLeftLeaves(root.left);
        int rightSum = sumOfLeftLeaves(root.right);

        return leftLeafVal + leftSum + rightSum;

    }
}

其他写法：

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

        int res = 0;
        
        // 递归出口
        if (root.left != null && root.left.left == null && root.left.right == null) {
            res += root.left.val;
        }
        if (root.left != null) {
            res += sumOfLeftLeaves(root.left);
        }
        if (root.right != null) {
            res += sumOfLeftLeaves(root.right);
        }

        return res;

    }
}

迭代

以前序遍历为例

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return 0;
        }
		
        int res = 0;
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                // 处理左叶子节点
                if (cur.left != null && cur.left.left == null && cur.left.right == null) {
                    res += cur.left.val;
                }
                // 左
                cur = cur.left;
            }
            else {
                // 右
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)
• 时间复杂度：O(N)