[Leetcode][第404题][JAVA][左叶子之和][DFS][BFS]

深藏阁楼爱情的钟 2022-12-08 12:53 140阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. DFS ######

**递进思想 一步一步递进**

/先序遍历求所有节点值之和

public int sumOfTrees(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int leave = root.val;
            int left = sumOfTrees(root.left);
            int right = sumOfTrees(root.right);
            return left + right + leave;
        }

在求节点之和的基础上，我们再来求所有叶子节点之和。

// 先序遍历求所有叶子节点值之和
        public int sumOfLeaves(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int leave = 0;
            // 叶子节点
            if (root.left == null && root.right == null) { 
                leave = root.val;
            }
            int left = sumOfLeaves(root.left);
            int right = sumOfLeaves(root.right);
            return left + right + leave;
        }

在求叶子节点之和的基础上，我们再来求所有左叶子节点之和。

当前节点是不是左节点，可以通过父节点标识。

public int sumOfLeftLeaves(TreeNode root) { 
            return sumOfLeftLeavesHelper(root, false);
        }
    
        // 先序遍历求所有左叶子节点值之和
        public int sumOfLeftLeavesHelper(TreeNode root, boolean flag) { 
            if (root == null) { 
                return 0;
            }
            int leave = 0;
            // 左叶子节点
            if (flag && root.left == null && root.right == null) { 
                leave = root.val;
            }
            int left = sumOfLeftLeavesHelper(root.left, true);
            int right = sumOfLeftLeavesHelper(root.right, false);
            return left + right + leave;
        }

通俗易懂版本

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        int sum=0;
        public int sumOfLeftLeaves(TreeNode root) { 
            if(root==null) return 0;
           dfs(root,0);
           return sum;
        }
        public void dfs(TreeNode root, int fPath){ 
              if(root.left==null && root.right==null && fPath==1){ 
                sum+=root.val;
              
            }
            if(root.right!=null){ 
                dfs(root.right,-1);
            }
            if(root.left!=null){ 
                dfs(root.left,1);
            }
        }
          
    
    }

###### 2. BFS ######

**时间复杂度：O(N) 空间复杂度：O(1)**

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;
        }
    }

#### 【总结】 ####

###### 1. 渐进思维 善用标志位（思维混乱的时候） ######

###### 2.树的问题 BFS DFS ######

转载链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/javadi-gui-yu-die-dai-shi-xian-si-lu-by-ggb2312/

参考链接：https://leetcode-cn.com/problems/sum-of-left-leaves/solution/zuo-xie-zi-zhi-he-by-leetcode-solution/  
来源：力扣（LeetCode）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/579bf9cf9f3046df9e8f0a318c7f552e.png