leecode404——左叶子之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了leecode404——左叶子之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🔍左叶子的定义：

首先要注意，是左叶子之和，而不是左侧节点之和。那么明确说，左叶子就是节点A的左孩子不为空，且左孩子的左节点为空并且左孩子的右节点为空，那么A的左孩子为左叶子节点。

1.如果使用递归法，则搬出递归三部曲：

🟣（1）确定函数参数和返回值

判断一棵树的左叶子节点和，那么传入的是树的根节点，函数返回的是根节点之和，因此返回类型为int类型。

🟣（2）确定终止条件

若根节点为空，则返回0。注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，

🟣（3）确定单层递归逻辑

当遇到左叶子的时候记录数值，递归求解左叶子之和，和右子树的左叶子节点之和。文章来源地址https://www.toymoban.com/news/detail-445430.html

2.使用迭代法

🟣（1）首先判空，若根节点为空，则返回0；

🟣（2）定义一个空栈，用于存储当前节点；当当前节点不为空时，将根节点压入栈中。定义一个res变量，计算当前左叶子节点的值。

🟣（3）开始循环，当栈不为空时，先取出当前节点，判断当前节点的左孩子是否为空，只有左孩子不为空并且左孩子的左右节点都为空时才能成为左叶子节点，若是左叶子，则将其计算加入res中。即

if(node.left!=null&&node.left.left==null&&node.left.right==null){
	res+=node.left.val;
}

🟣（4）当不是左叶子节点时，继续往下遍历，判断该节点的左右节点是否为空，不为空加入栈中，弹出该节点，`判断下一个节点的（3）步骤`，直到到达左右叶子节点，跳出村换返回结果。

if (node.right != null) stack.add(node.right);
if (node.left != null) stack.add(node.left);

完整代码如下;

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