数据结构与算法 -- Leetcode中二叉树相关问题解题套路（2）

二叉搜索树

什么是二叉搜索树？它其实是二叉树的一种比较特殊的形式：

• 左子树上的所有节点的值均小于其根节点的值；
• 右子树上的所有节点的值均大于其根节点的值；
• 准确的说，其左右子树均为二叉搜索树。

那么二叉搜索树有什么特性呢?

其中序遍历的集合，为升序排序。这个特性非常重要，可以帮我们处理很多复杂的问题。

问题1：求二叉搜索树中不同节点之间绝对差最小

其实如果了解二叉搜索树的特性，进行一次中序遍历，因为是升序排序，因此期间不断比较两个相邻节点之间的差值，就可以找到对应的最小差值。

public int getMinimumDifference(TreeNode head) {
       
    Stack<TreeNode> stack = new Stack();
    int abs = Integer.MAX_VALUE;
    int pre = -1;

    while(!stack.isEmpty() || head != null){
        if(head != null){
            stack.push(head);
            head = head.left;
        }else{
            //弹出节点
            TreeNode node = stack.pop();
            if(pre < 0){
                pre = node.val;
            }else{
               if( Math.abs(node.val - pre) < abs){
                   abs = Math.abs(node.val - pre);
               }
               pre = node.val;
            }
            head = node.right;
        }
    }
    return abs;
}

问题2：求搜索二叉树中第k小的节点

其实这道题也很简单，就是在节点弹出的时候，记录一个pos，如果pos等于k，那么就直接返回即可；我们不需要关心k是否超出二叉树的节点总数，while循环结束之后还没完成匹配，直接返回0即可。

public int kthSmallest(TreeNode root, int k) {
    if(root == null){
        return 0;
    }
    Stack<TreeNode> stack = new Stack();
    int pos = 0;

    while(!stack.isEmpty() || root != null){
        if(root != null){
            stack.push(root);
            root = root.left;
        }else{
            //开始弹出
            TreeNode node = stack.pop();
            pos++;
            if(pos == k){
                return node.val;
            }
            root = node.right;
        }
    }

    return 0;
}

逆向思维验证二叉树是否为二叉搜索树

因为中序遍历，所有的节点是升序的，因此每次弹出节点都与上次节点做一次比较，如果不是递增的话，注意节点值不能相等， 那么就认为不是二叉搜索树。

public boolean isValidBST(TreeNode root) {
    if(root == null){
        return true;
    }

    Stack<TreeNode> stack = new Stack();
    Integer pre = null;

    while(!stack.isEmpty() || root != null){

        if(root != null){
            stack.push(root);
            root = root.left;
        }else{

            TreeNode node = stack.pop();
            if(pre == null){
                pre = node.val;
            }else{
                if(node.val <= pre){
                    return false;
                }
                pre = node.val;
            }
            root = node.right;
        }

    }
    return true;
}

根据前序、中序、后序数组构建二叉树

对于通过数组构建二叉树的问题，大致分为两种：

• 通过前序和中序数组构建二叉树，或者通过后序和中序数组构建二叉树；
• 通过数组构建平衡二叉搜索树。

想一个问题，为啥一定需要中序数组，通过前序和后序无法构建吗？是的，其实前序和后序更多的是起辅助作用，目的就是为了找到根节点在中序数组中的位置， 从而通过迭代的方式构建二叉树。

题目

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

解题思路

给定了先序遍历，我们知道其顺序为头左右，所以根节点就是前序数组第一个元素，那么如何知道中序遍历中头结点的位置呢？我们可以通过哈希表来存储对应的节点和位置的映射关系。

private Map<Integer,Integer> map = new HashMap<>();

/**
 * 根据前序数组和中序数组构建二叉树
 * @param preorder 前序数组
 * @param inorder 中序数组
 * @return 二叉树
 */
public TreeNode buildTree(int[] preorder, int[] inorder){
    //有一个为空，就没法构建
    if(preorder == null || inorder == null){
        return null;
    }
    //存储中序数组的val和其位置的映射
    for (int i = 0;i<inorder.length;i++){
        map.put(inorder[i],i);
    }
    //开始构建二叉树
    return buildInner(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}

/**
 * 内部构建二叉树
 * @param preorder 前序数组
 * @param inorder 中序数组
 * @param ps 前序数组的起始位置
 * @param pe 前序数组的终点位置
 * @param is 后序数组的起始位置
 * @param ie 后序数组的终点位置
 */
private TreeNode buildInner(int[] preorder,int[] inorder,int ps,int pe,int is,int ie){
    if(ps > pe || is > ie){
        return null;
    }
    //找到根节点
    int rootVal = preorder[ps];
    //在中序数组中的位置
    int index = map.get(rootVal);
    //左子树的长度
    int leftChildLength = index-is;
    TreeNode root = new TreeNode(rootVal);
    //构建左子树
    root.left = buildInner(preorder,inorder,ps+1,ps+leftChildLength,is,is+leftChildLength-1);
    root.right = buildInner(preorder,inorder,ps+leftChildLength+1,pe,index+1,ie);
    return root;
}

在构建二叉树时，我们只需要找到前序数组中左子树的位置和中序数组中左子树的位置以及前序数组中右子树的位置和中序数组中右子树的位置即可通过迭代完成。

题目

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路

这道题构建的二叉树不是固定的，任意二叉树均可以，但是需要构建一棵平衡二叉搜索树，根据我们前面介绍二叉搜索树的特性，题目中给到的是一个升序数组，那么这个数组就是这棵树的中序遍历数组。同时又要保持平衡，因此只需要将数组一分为2，左半部分构建左树，右半部分构建右树，中间的数字即为这棵二叉树的根节点。

public TreeNode sortedArrayToBST(int[] nums) {
    //平衡二叉搜索树，即高度差不能超过1，因此找到数组的中间元素，作为根节点，
    //然后左右构建二叉树
    return buildTree(nums,0,nums.length-1);
}

private TreeNode buildTree(int nums[],int start,int end){
    if(start > end){
        return null;
    }

    int middle = (end + start) / 2;
    TreeNode root = new TreeNode(nums[middle]);
    root.left = buildTree(nums,start,middle-1);
    root.right = buildTree(nums,middle+1,end);
    return root;
}