【算法&数据结构初阶篇】：二叉树

朱雀 2024-03-27 14:06 123阅读 0赞

### 105. 从前序与中序遍历序列构造二叉树 ###

[LeetCode:105. 从前序与中序遍历序列构造二叉树][LeetCode_105.]

![b5510fbef3c699e8ddb5f6cc39996754.png][]

![30fb4979cd29a03a8ea550ecea04c61e.png][]

> 核心点：  
> 1. 前序遍历：根左右 ；中序遍历：左根右  
>   
> 2.从前序遍历中的子树preorder，第一个元素即为根节点， 创建出根节点head,最后用来返回  
>   
> 3.接着就从 中序遍历中的子树inorder，遍历找到根节点对应的索引find,\[L2,find)即为左子树元素，(find,R2\]即为右子树元素，find - L2的根节点到左子树边界距离长度就等同于中序遍历中根节点到左子树边界距离，从而来 确定左子树的右边界： L1 + find - L2 ，其余边界同理推断  
>   
> 4.然后开始用根节点 head递归去构造head.left head.right左右子树  
>   
> 5. L1 > R1边界溢出，这点很重要容易忽略，会出现 二叉树是一个单边树，即左子树空或者右子树空，此时就会存在越界情况：比如先序 中序 都为\[1,2,3\] (左子树为空) ，根节点1，中序遍历中索引find=0，再往左找左子树递归就溢出了。head.left = f(preorder, L1 + 1, L1 + find - L2, inorder, L2, find - 1,valueIndexMap); 此时L1 + find - L2 = L1 因为第一轮find跟L2重叠 所以就变成 L1+1,L1 溢出，则需要返回空

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            //提前记录中序遍历的头节点对应索引的Map,用来查询出中序遍历中哪个是根节点，对应的索引，就不用每次递归子树时都要循环查找中序遍历的根节点
            HashMap<Integer,Integer> valueIndexMap = new HashMap<>();
            for(int i = 0; i < inorder.length; i++){
                valueIndexMap.put(inorder[i], i);
            }
            return f(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, valueIndexMap);
            
        }
        // 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
        // 请建出整棵树返回头节点
        public TreeNode f(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2, HashMap<Integer,Integer> valueIndexMap){
            //存在某些情况下 会越界溢出
            //比如 先序 中序 都为[1,2,3] (左子树为空) 那么确定好根节点1，中序遍历中该根节点在索引find=0，在往左找左子树递归就溢出了。head.left =  f(preorder, L1 + 1, L1 + find - L2, inorder, L2, find - 1,valueIndexMap); 此时L1 + find - L2 = L1  因为第一轮find跟L2重叠 所以就变成L1+1,L1 溢出，返回空
            if(L1 > R1) 
            return null;
            //先序遍历 根左右，索引第一个即为根节点 取出
            TreeNode head = new TreeNode(preorder[L1]);
            //当子树中只有自己的时候则直接返回根节点
            if(L1 == R1)
            return head;
            //从中序遍历中，找到根节点L1对应的索引find ,那么 从[0,find-1]皆为左子树的节点，
            //[find+1,R2]皆为右子树的节点，然后就开始分别左递归，右递归去构建树
            int find = valueIndexMap.get(preorder[L1]);
            //递归左子树：确定先序遍历的左子树左右边界：左边界就是从L1+1,因为L1是根节点，根据中序遍历根节点索引find往左的元素都为左子树元素，find - L2 表示根节点到左子树左边界的距离，那么在先序遍历中根节点加上这个距离就得到左子树的右边界了。 因为两边同个子树长度一定相等。 所以右边界为 L1+find-L2;    而中序遍历的左子树左右边界：就是find节点左侧那一堆数 L2,find-1
            //
            head.left = f(preorder, L1 + 1, L1 + find - L2, inorder, L2, find - 1,valueIndexMap);
            //递归右子树同理
            head.right = f(preorder,L1 + find - L2 + 1, R1, inorder, find + 1, R2,valueIndexMap);
            //最后需要返回根节点
            return head;
    
        }
    }

### 98. 验证二叉搜索树 ###

[LeetCode:98.验证二叉搜索树][LeetCode_98.]

![c316aaa092b752b308e946ad73f782f6.png][]

![7e1c0e789b6eb456839fa5a91b3346d2.png][]

代码如下：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public boolean isValidBST(TreeNode root) {
            return process(root).isBST;
        }
    
        //定义一个类，存放树是否为搜索树、树的最大值、最小值 
        public class info{
            public boolean isBST;
            public int max;
            public int min;
            public info(boolean is, int ma, int mi){
                isBST = is;
                max = ma;
                min = mi;
            }
        }
        //递归树
        public info process(TreeNode x){
            //当前节点空时，则返回null，返回给到上一层去处理
            if(x == null) return null;
            //开始递归左右子树
            info leftInfo = process(x.left);
            info rightInfo = process(x.right);
            //判断是否为搜索树，初始默认为true，后面再判断不满足的条件 再赋值false
            Boolean isBST = true;
            //初始默认当前节点为该节点树的最大值与最小值
            int max = x.val;
            int min = x.val;
            //如果左右子树非空，就分别判断刷新最大值与最小值，左子树的最大值，如果大于当前节点max,其实就是当前节点值，那么max就会刷新，这种情况就不是搜索树，因为左子树是要小于父节点 
            if(leftInfo != null){
                max = Math.max(max, leftInfo.max);
                min = Math.min(min,leftInfo.min);
            }
            if(rightInfo != null){
                max = Math.max(max, rightInfo.max);
                min = Math.min(min,rightInfo.min);
            }
            //1.左右子树非空且isBsT为false 即左右子树为非搜索树，那这个父节点的树也为非搜索树
            if(leftInfo != null && !leftInfo.isBST) isBST = false;
            if(rightInfo != null && !rightInfo.isBST) isBST = false;
            //2.判断左子树是否小于父节点，右子树是否大于父节点
            Boolean leftMaxLessX = leftInfo == null ? true : leftInfo.max < x.val;
            Boolean rightMinMoreX = rightInfo == null ? true : rightInfo.min > x.val;
            //3.当前 左子树小于父节点且右子树大于父节点时 才是搜索树，所以取反情况下则非搜索树
            if(!(leftMaxLessX && rightMinMoreX)) isBST = false;
            //最后返回当前节点三个自定义的信息
            return new info(isBST, max, min);
    
        }
    }

### 110. 平衡二叉树 ###

[LeetCode:110. 平衡二叉树][LeetCode_110.]

![ac0220320c95a9560635e1eb21444818.png][]

![7d54b064fd3978171aa94b113bbac596.png][]

![62dcbf26b4fd12677e341237eae2d371.png][]

代码如下：

### 112. 路径总和 ###

[112. 路径总和][112.]

代码如下：两种

package class07;
    
    public class Code03_PathSum {
    
        // 测试链接：https://leetcode.com/problems/path-sum
        public static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
    
            TreeNode(int val) {
                this.val = val;
            }
        }
    
        public static boolean isSum = false;
    
        public static boolean hasPathSum(TreeNode root, int sum) {
            if (root == null) {
                return false;
            }
            isSum = false;
            process(root, 0, sum);
            return isSum;
        }
    
        public static void process(TreeNode x, int preSum, int sum) {
            if (x.left == null && x.right == null) {
                if (x.val + preSum == sum) {
                    isSum = true;
                }
                return;
            }
            // x是非叶节点
            preSum += x.val;
            if (x.left != null) {
                process(x.left, preSum, sum);
            }
            if (x.right != null) {
                process(x.right, preSum, sum);
            }
        }
    
    //    public static boolean hasPathSum(TreeNode root, int sum) {
    //        if (root == null) {
    //            return false;
    //        }
    //        return process(root, sum);
    //    }
    //
    //    public static boolean process(TreeNode root, int rest) {
    //        if (root.left == null && root.right == null) {
    //            return root.val == rest;
    //        }
    //        boolean ans = root.left != null ? process(root.left, rest - root.val) : false;
    //        ans |= root.right != null ? process(root.right, rest - root.val) : false;
    //        return ans;
    //    }
    
    }

### 113. 路径总和 II ###

[113. 路径总和 II][113. _ II]

代码如下：两种

package class07;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Code04_PathSumII {
    
        // 测试链接：https://leetcode.com/problems/path-sum-ii
        public static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
    
            TreeNode(int val) {
                this.val = val;
            }
        }
    
        public static List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            ArrayList<Integer> path = new ArrayList<>();
            process(root, path, 0, sum, ans);
            return ans;
        }
    
        public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
            if (x.left == null && x.right == null) {
                if (preSum + x.val == sum) {
                    path.add(x.val);
                    ans.add(copy(path));
                    path.remove(path.size() - 1);
                }
                return;
            }
            // x 非叶节点
            path.add(x.val);
            preSum += x.val;
            if (x.left != null) {
                process(x.left, path, preSum, sum, ans);
            }
            if (x.right != null) {
                process(x.right, path, preSum, sum, ans);
            }
            path.remove(path.size() - 1);
        }
    
        public static List<Integer> copy(List<Integer> path) {
            List<Integer> ans = new ArrayList<>();
            for (Integer num : path) {
                ans.add(num);
            }
            return ans;
        }
    
    }

### 107. 二叉树的层序遍历 II ###

[107. 二叉树的层序遍历 II][107. _ II]

代码如下：

[LeetCode_105.]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
[b5510fbef3c699e8ddb5f6cc39996754.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/55c181f6b6c7490f856910d1d5a17c3c.png
[30fb4979cd29a03a8ea550ecea04c61e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e0edae5337c142f8889beb1d8f3233b1.png
[LeetCode_98.]: https://leetcode.cn/problems/validate-binary-search-tree/description/
[c316aaa092b752b308e946ad73f782f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/568cbb45ca46429eacbb65b8fc63fe76.png
[7e1c0e789b6eb456839fa5a91b3346d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/78d43a2582c849dcb914cd05a3fbcd79.png
[LeetCode_110.]: https://leetcode.cn/problems/balanced-binary-tree/
[ac0220320c95a9560635e1eb21444818.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/119e94e0035f4e3698866366a873921a.png
[7d54b064fd3978171aa94b113bbac596.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/70eccbcc74884dd99343cb832c6fe115.png
[62dcbf26b4fd12677e341237eae2d371.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2562ed7162ba468da16338b908f78820.png
[112.]: https://leetcode.cn/problems/path-sum/description/
[113. _ II]: https://leetcode.cn/problems/path-sum-ii/description/
[107. _ II]: https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/