剑指：二叉树有关题目

题目链接：JZ7 重建二叉树

题目描述：给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
前提条件：
pre 和 vin 均无重复元素
vin出现的元素均出现在 pre里
只需要返回根结点，系统会自动输出整颗树做答案对比
要求：空间复杂度 O(n)，时间复杂度 O(n)
题目分析：已知前序遍历和中序遍历可以唯一确定一棵二叉树，前序遍历可以首先确定root结点，在中序遍历中找到root结点值的下标，就可以划分左右子树结点集合，以此类推，递归遍历。
递归函数功能：原函数功能（根据前序数组和中序数组重建二叉树）
递归出口：pre.length为0 或 vin.length为0
递归入口：在中序遍历数组中找到当前root值的索引，通过 Arrays.copyOfRange() 函数传pre数组和vin数组

public class Solution {
   
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
   
        //重建二叉树
        if(pre.length==0||vin.length==0){
   
            return null;
        }
        TreeNode root = new TreeNode(pre[0]); //根节点
        for(int i=0; i<vin.length; i++){
   
            if(vin[i]==pre[0]){
   
                //递归左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                //递归右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目链接：JZ54 二叉搜索树的第k个节点

题目描述：给定一棵结点数为n 二叉搜索树 ，请找出其中的第 k 小的TreeNode结点值。不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1。
题目分析：
①递归遍历。二叉搜索树左中右遍历值依次从小到大，所以我们在中序遍历的基础上，增加遍历结点个数count的限制，返回第k个最小结点。时间复杂度为O(n)， 空间复杂度为O(n)；

public class Solution {
   
    //指向目标结点（第k个的结点）
    TreeNode res = null;
    //记录遍历过的结点（从最小的结点开始遍历）
    private int count = 0;
    //中序遍历
    public void midOrder(TreeNode root, int k){
   
        if(root==null || count>k){
   
            return;
        }
        midOrder(root.left,k);
        count++;
        if(count==k){
   
            res = root; //标记第k个结点
        }
        midOrder(root.right,k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19