二叉树习题总结

目录

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

1.题目

2.思路图解

3.代码

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

1.题目

2.思路图解

3.代码

三.二叉树的的最大路径和

1.题目

2.思路图解

3.代码

四.括号生成

1.题目

2.思路图解

3.代码

五. 不同的二叉搜索树

1.题目

2.思路图解

3.代码

（1）优化前

（2）优化后

六.验证二叉搜索树

1.题目

2.思路图解

3.代码

七.二叉树展开为链表

1.题目

2.思路图解

3.代码

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

1.题目

给定一个二叉树的中序与后序遍历结果，请你根据两个序列构造符合这两个序列的二叉树。

示例：

例如输入[2,1,4,3,5],[2,4,5,3,1]时，

根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5}

2.思路图解

因为后序遍历的最后一个元素是根节点，所以我们可以根据后序序列确定根节点，然后再从中序遍历中寻找该根节点，然后划分区间，最后根据区间递归构造当前根节点的左右子树即可。

3.代码

    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
        //说明当前区间的左右子树已经构造完成
        if(inRight-inLeft<1) {
            return null;
        }
        //说明当前子树的左边只剩下一个结点，直接构造为根节点
        if(inRight-inLeft==1) {
            return new TreeNode(inorder[inLeft]);
        }
        //在中序数组中找根节点所在的位置
        int pos = 0;
        for(int i=inLeft; i<inRight; i++) {
            if(inorder[i] == postorder[postRight-1]) {
                pos = i;
                break;
            }
        }
        TreeNode root = new TreeNode(inorder[pos]);
        //找到根节点所在位置后，开始划分中序数组和后序数组的区间
        root.left = build(inorder, inLeft, pos, postorder, postLeft, postLeft+(pos-inLeft));
        root.right = build(inorder, pos+1, inRight, postorder, postLeft+(pos-inLeft), postRight-1);
        return root;
    }

 

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

1.题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

2.思路图解

划分区间的思想：这里首先使用map来保存中序数组的值和下标，方便之后找以中序位置划分区间；然后递归构造二叉树，当前序的左边界=右边界，说明当前区间已经构造完成，直接返回，否则就先根据前序（前序的子区间的第一个结点为根结点）构造出根结点，然后再递归构造该根根结点的左右子树，最后返回根结点即可。

 

3.代码

     Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0; i<inorder.length; i++) {
            map.put(inorder[i], i);
        }
       return dfs(preorder, 0,preorder.length, inorder, 0, inorder.length);
        
    }
    public TreeNode dfs(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){
        if(inRight-inLeft==0) {
            return null;
        }
        
        //获取中序遍历的位置
        int pos = map.get(preorder[preLeft]);
        //划分区间并构造根结点
        TreeNode root = new TreeNode(inorder[pos]);
        root.left = dfs(preorder, preLeft+1, preLeft+(pos-inLeft)+1, inorder, inLeft, pos);
        root.right = dfs(preorder, preLeft+(pos-inLeft)+1, preRight, inorder, pos+1, inRight);
        return root;
    }

 

 

三.二叉树的的最大路径和

1.题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：

2.思路图解

3.代码

 int maxRes = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxRes;
    }
    public int dfs(TreeNode root) {
        //空结点不做贡献
        if(root == null) {
            return 0;
        }
        //统计左右子树分别的贡献，如果小于0就不统计
        int left = Math.max(dfs(root.left),0);
        int right = Math.max(dfs(root.right),0);
        //判断是否当前路径的值比保存的结果值大
        maxRes = Math.max(maxRes, root.val+left+right);
        
        //返回当前子树中的最大路径和
        return root.val+Math.max(left, right);
        
    }

四.括号生成

1.题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

2.思路图解

首先递归处理左括号，在处理完左括号后，右括号的处理需要依据左括号进行处理，当左括号处理的个数多于右括号处理的个数时，再处理右括号，相当于左括号优先匹配，因为要先有左括号后，然后右括号才能匹配，处理图解如下：

3.代码

  public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(n, n, new StringBuilder(), res);
        return res;
    }
    public void dfs(int left, int right, StringBuilder sb, List<String> res) {
        if(left==0 && right==0) {
            res.add(new String(sb));
            return;
        }
        if(left>0) {
            sb.append('(');
            dfs(left-1, right, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right>left) {
            sb.append(')');
            dfs(left, right-1, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
    }

五. 不同的二叉搜索树

1.题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例：

2.思路图解

二叉搜索树就是左子树的结点<当前根结点<右子树的结点；因为每一个都可能作为根结点，所以每次计算以当前结点为根结点能够构成的所有二叉搜索树的个数，之后求所有结果和即可；对于当前结点求二叉搜索树个数的方式是：先求当前结点左边结点组成二叉搜索树的个数，再求当前结点右边结点组成二叉搜索树的个数，最后左边*右边的个数就是当前结点的所有二叉搜索树构成的个数。

优化：由于每一个元素都会作为根结点，所以有些子树中的二叉搜索树多次重复求解，这里借助map集合来保存求得的二叉搜索树，如果当前结点的二叉搜索树已经求过，就直接在map中取出即可，否则就添加到map中。

3.代码

（1）优化前

public int numTrees(int n) {
        //根结点只有1个或0个
        if(n==0 || n==1) {
            return 1;
        }
        int count = 0;
        for(int i=1; i<=n ;i++) {
            //计算以当前结点为根节点的左右子树可以构成的个数
            int leftCount = numTrees(i-1);
            int rightCount = numTrees(n-i);
            count += leftCount*rightCount;
        }
        return count;
    }

（2）优化后

//设置成全局变量，保存记录 
HashMap<Integer,Integer> map = new HashMap<>();
    public int numTrees(int n) {
        //根结点只有1个或0个
        if(n==0 || n==1) {
            return 1;
        }
        //说明以当前为根的二叉搜索树的个数已经查找过了
        if(map.containsKey(n)) {
            return map.get(n);
        }
        int count = 0;
        for(int i=1; i<=n ;i++) {
            //计算以当前结点为根节点的左右子树可以构成的个数
            int leftCount = numTrees(i-1);
            int rightCount = numTrees(n-i);
            count += leftCount*rightCount;
        }
        map.put(n, count);
        return count;
    }

六.验证二叉搜索树

1.题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路图解

根据二叉搜索树的性质：左<当前<右，中序结果是有序的，所以在查找的时候保留前一个结点，之后当前结点的值与前一个结点的值进行比较，如果前一个结点的值>=当前结点的值，说明不符合结果，返回false；最终处理的方式是先处理左子树，如果左子树不满足条件，直接返回false；若左子树有序，则处理当前结点，之后再处理右子树。

3.代码

 TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        //说明左子树不满足二叉树性质，直接返回
        if(!isValidBST(root.left)) {
            return false;
        }
        //判断当前结点与前一个结点的大小
        if(pre!=null && pre.val>= root.val) {
            return false;
        }
        pre = root;
        //无论右子树的情况，直接返回
        return isValidBST(root.right);
    }

 

七.二叉树展开为链表

1.题目

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：

 

2.思路图解

先前序遍历保存所有结点，然后再以前一个节点为前驱(pre)，先修改的pre.left为空，然后再让pre.right指向当前结点（cur）,最后所得结果就是单链表。

3.代码

public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preorder(root, list);
        //第一个节点为前驱结点，修改前一个节点的left为null, right指向当前结点
        for(int i=1; i<list.size(); i++) {
            TreeNode pre = list.get(i-1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
    public void preorder(TreeNode root, List<TreeNode> list){
        if(root == null) {
            return;
        }
        //根左右
        list.add(root);
        preorder(root.left, list);
        preorder(root.right, list);
    }