二叉树习题其三-Java【力扣】【算法学习day.10】

前言

书接上篇文章二叉树习题其二，这篇文章我们将基础拓展

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.从中序与后序遍历序列构造二叉树

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

题面:

基本分析：后序遍历数组的最后一个值其实就是根节点，由于中序遍历的顺序是前中后，那么我们在中序数组中定位到根节点的位置，例如上图样例是3，那么在 3左边的就是左子树，右边的就是右子树，这就是递归的一个过程，然后使用递归

/**
 * 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 {
    Map<Integer,Integer> map = new HashMap<>();
    int[] postorderflag;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length-1;
        for(int i = 0;i<=n;i++)map.put(inorder[i],i);
        postorderflag = postorder;
        return recursion(0,n,0,n);
        }
        public TreeNode recursion(int is,int ie,int ps,int pe){
            if(is>ie||ps>pe)return null;
            int root = postorderflag[pe];
            TreeNode node = new TreeNode(root);
            int ri = map.get(root);
            node.left = recursion(is,ri-1,ps,ps+ri-is-1);
            node.right = recursion(ri+1,ie,ps+ri-is,pe-1);
            return node;
        }    
    }

2.最大二叉树

题目链接：654. 最大二叉树 - 力扣（LeetCode）

题面:

基本分析:就是区间找最值然后构造树

代码:

/**
 * 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 {
     int numsflag[];
     Map<Integer,Integer> map = new HashMap<>();
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        numsflag = nums;
        int n = nums.length-1;
        for(int i = 0;i<=n;i++)map.put(nums[i],i);
        return recursion(0,n);
    }
    public TreeNode recursion(int l,int r){
        if(l>r)return null;
        int max = Integer.MIN_VALUE;
        for(int i = l;i<=r;i++){
            if(numsflag[i]>max)max = numsflag[i];
        } 
        int index = map.get(max);
        TreeNode node = new TreeNode(max);
        node.left = recursion(l,index -1);
        node.right = recursion(index+1,r);
        return node;
    }
    
}

3.合并二叉树

题目链接：617. 合并二叉树 - 力扣（LeetCode）

题面:

基本分析：两者同时遍历

/**
 * 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 mergeTrees(TreeNode root1, TreeNode root2) {
        return recursion(root1,root2);
    }
    public TreeNode recursion(TreeNode root1, TreeNode root2){
        TreeNode node = new TreeNode(Integer.MAX_VALUE);
        if(root1==null&&root2==null)return null;
        if(root1==null||root2==null){
            return root1==null?root2:root1;
        }
        node.val=(root2.val+root1.val);
        node.left = recursion(root1.left,root2.left);
        node.right = recursion(root1.right,root2.right);
        return node;
    }

}

4.二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

题面:

基本分析:就是遍历

代码: 

/**
 * 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 {
    TreeNode ans = new TreeNode(Integer.MAX_VALUE);
    int flag = 0;
    public TreeNode searchBST(TreeNode root, int val) {
        flag = val;
        recursion(root);
        return ans.val==Integer.MAX_VALUE?null:ans;
    }
    public void recursion(TreeNode node){
        if(node==null)return;
        if(node.val==flag)ans = node;
        recursion(node.left);
        recursion(node.right);
    }
}

 5.验证二叉搜索树

题目链接:98. 验证二叉搜索树 - 力扣（LeetCode）

题面:

基本分析：采用限定范围的思想可以规避很多变量的维护

代码:

/**
 * 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 {
    ArrayList<Integer> listleft = new ArrayList<>();
    ArrayList<Integer> listright = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
       return recursion(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean recursion(TreeNode node,long left,long right){
        if(node==null)return true;
        long flag = node.val;
        return flag>left&&flag<right&&recursion(node.left,left,flag)&&recursion(node.right,flag,right);
    }
}

后言

上面是二叉树的部分习题，下一篇会讲解二叉树的其他相关力扣习题，希望有所帮助，一同进步，共勉！