Day27——二叉树专题

系统管理员 2024-04-01 14:49 65阅读 0赞

#### 文章目录 ####

*   *   *   *  11.二叉树的所有路径
             *  12.左叶子之和
             *  13.找树的左下角的值

--------------------

##### 11.二叉树的所有路径 #####

**思路：**

根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径，求**所有**路径，就是暴力搜索每一种可能，我们可以用深度优先搜索实现（前序遍历），由于要递归枚举每一种可能，注意回溯恢复现场即可！

![image-20221104182145982][]

1.  递归函数函数参数以及返回值
2.  确定递归终止条件
3.  确定单层递归逻辑

class Solution {
        
        
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> res = new ArrayList<>();
            dfs(root, "", res);
            return res;
        }
        public void dfs(TreeNode root, String path, List<String> list){
        
            if(root == null){
        
                return ;
            }
            //递归出口：如果是叶子节点，说明是一条路径，加入res集合
            if(root.left == null && root.right == null){
        
                list.add(path + root.val);
                return ;
            }
            
            // 当递归到递归出口（叶子节点）后就会回溯，自带的
            
            dfs(root.left, path + root.val + "->", list);
            dfs(root.right, path + root.val + "->", list);
        }
    }

##### 12.左叶子之和 #####

**思路：**`dfs`（前序遍历求和即可），求和的条件是节点为左叶子节点

**代码实现：**

**递归**

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

**迭代**

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

##### 13.找树的左下角的值 #####

**思路**：按照先左后右的顺序遍历子树，最先搜索到的最深的结点即所求的结点。

**代码实现：**

**递归法**

// 递归法
    class Solution {
        
        private int Deep = -1;
        private int value = 0;
        public int findBottomLeftValue(TreeNode root) {
        
            value = root.val;
            findLeftValue(root,0);
            return value;
        }
    
        private void findLeftValue (TreeNode root,int deep) {
        
            if (root == null) return;
            if (root.left == null && root.right == null) {
        
                if (deep > Deep) {
        
                    value = root.val;
                    Deep = deep;
                }
            }
            if (root.left != null) findLeftValue(root.left,deep + 1);
            if (root.right != null) findLeftValue(root.right,deep + 1);
        }
    }

**迭代法**

//迭代法
    class Solution {
        
    
        public int findBottomLeftValue(TreeNode root) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int res = 0;
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode poll = queue.poll();
                    if (i == 0) {
        
                        res = poll.val;
                    }
                    if (poll.left != null) {
        
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
        
                        queue.offer(poll.right);
                    }
                }
            }
            return res;
        }
    }

[image-20221104182145982]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9291f95ebef84052a7fc5e485744217b.png