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

缺乏、安全感 2023-10-08 16:12 18阅读 0赞

## 1 题目描述 ##

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

## 2 题目示例 ##

![在这里插入图片描述][c8a08b9103194fdf890952bd0c14aa8e.png]  
示例 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;
        }
    }

[c8a08b9103194fdf890952bd0c14aa8e.png]: https://img-blog.csdnimg.cn/c8a08b9103194fdf890952bd0c14aa8e.png