二叉树——404. 左叶子之和

1 题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

2 题目示例

示例 2:

输入: root = [1]
输出: 0

3 题目提示

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

4 思路

一个节点为「左叶子」节点，当且仅当它是某个节点的左子节点，并且它是一个叶子结点。因此我们可以考虑对整棵树进行遍历，当我们遍历到节点node时，如果它的左子节点是一个叶子结点，那么就将它的左子节点的值累加计入答案。
深度：
复杂度分析

• 时间复杂度:o(n)，其中n是树中的节点个数。
• 空间复杂度:O(n)。空间复杂度与深度优先搜索使用的栈的最大深度相关。在最坏的情况下，树呈现链式结构，深度为O(n)，对应的空间复杂度也为O(n)。
  广度：
  复杂度分析
• 时间复杂度:O(n)，其中n是树中的节点个数。
• 空间复杂度:O(n)。空间复杂度与广度优先搜索使用的队列需要的容量相关，为O(n)。

递归：
递归的遍历顺序为后序遍历(左右中)，是因为要通过递归函数的返回值来累加求取左叶子数值之和。。
递归三部曲:

1. 确定递归函数的参数和返回值
   判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int
   使用题目中给出的函数就可以了。

2. 确定终止条件
   依然是

   if (root NLLL) return O ;
   

3. 确定单层递归的逻辑
   当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

5 我的答案

深度：

class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
    
        return root != null ? dfs(root) : 0;
    }

    public int dfs(TreeNode node) {
    
        int ans = 0;
        if (node.left != null) {
    
            ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
        }
        if (node.right != null && !isLeafNode(node.right)) {
    
            ans += dfs(node.right);
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
    
        return node.left == null && node.right == null;
    }
}

广度：

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

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
    
            TreeNode node = queue.poll();
            if (node.left != null) {
    
                if (isLeafNode(node.left)) {
    
                    ans += node.left.val;
                } else {
    
                    queue.offer(node.left);
                }
            }
            if (node.right != null) {
    
                if (!isLeafNode(node.right)) {
    
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }

    public boolean isLeafNode(TreeNode node) {
    
        return node.left == null && node.right == null;
    }
}

普通递归：

class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
    
        if (root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);    // 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右
                                                       
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
     // 中
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}