第10章二叉树 - 二分搜索树 - 《数据结构与算法》

LeetCode

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        // 只在左边
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // 只在右边
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

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

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return dfs(root, null, null);
    }
    private boolean dfs(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        if (min != null && node.val <= min) {
            return false;
        }
        if (max != null && node.val >= max) {
            return false;
        }
        return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
    }
}

108. 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

思路：
采用分而治之的策略，利用了归并排序的思想。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sAToBST(nums, 0, nums.length - 1);
    }
    public TreeNode sAToBST(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = left + (right - left + 1)/2;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = sAToBST(nums, left, mid - 1);
        cur.right = sAToBST(nums, mid + 1, right);
        return cur;
    }
}

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

思路：
中序遍历。借助 ArrayList 存放遍历到的元素，也可以声明一个成员变量进行计数。

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        helper(root, res);
        return res.get(k-1);
    }
    public void helper(TreeNode node, ArrayList<Integer> res) {
        if(node == null) return;
        if(node.left != null) {
            helper(node.left, res);
        }
        res.add(node.val);
        if(node.right != null) {
            helper(node.right, res);
        }
    }
}

练习：

173. 二叉搜索树迭代器

450. 删除二叉搜索树中的节点

剑指 Offer

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路：
递归。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }
    private boolean helper(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int p = i;
        while (postorder[p] < postorder[j]) {
            p++;
        }
        int m = p;
        while (postorder[p] > postorder[j]) {
            p++;            
        }
        return p == j && helper(postorder, i, m - 1) && helper(postorder, m, j - 1);
    }
}

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

思路：
深度优先搜索。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node pre = null, head = null;  //pre记录上一个节点，head为最后返回的头结点
    public Node treeToDoublyList(Node root) {
        if(root == null) return root;
        helper(root);  //得到一个双向链表，head指向头结点
        head.left = pre;
        pre.right = head;  //形成循环链表
        return head;
    }
    public void helper(Node root){
        if(root == null) return;  //到了最后的时候，就返回
        helper(root.left);  //规整左子树
        root.left = pre;
        if(pre != null){
            pre.right = root;  //当前面还有节点的时候，连接上
        }
        else
            head = root;   //如果前面没有节点了，证明是头结点，就更新head
        pre = root;   //root可以视为一个节点了
        helper(root.right);  //规整右子树
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

思路：
中序遍历。
执行用时：1 ms, 在所有 Java 提交中击败了46.67%的用户
内存消耗：40.4 MB, 在所有 Java 提交中击败了100.00%的用户

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(list, root);
        return list.get(list.size() - k);
    }
    private void dfs(List<Integer> list, TreeNode root) {
        if (root.left != null) {
            dfs(list, root.left);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(list, root.right);
        }
    }
}

思路2：
中序遍历，提前返回。

class Solution {
    private int res, n;

    public int kthLargest(TreeNode root, int k) {
       n = k;
       dfs(root);
       return res;
    }

    public void dfs(TreeNode node) {
        if (node == null || n <= 0) return;
        dfs(node.right);
        if (--n == 0) {
            res = node.val;
            return;
        }
        dfs(node.left);
    }
}

思路3：
非中序遍历。
先得出右子树的节点个数，如果恰好等于k-1，则说明该节点为第k大的节点；
如果右子树节点个数大于k-1则继续搜索右子树第k大节点；
如果右子树节点个数小于k-1，则搜索左子树中第k-numright-1大的节点。

class Solution {
    public int kthLargest(TreeNode root, int k) {
        int numright= nodeNum(root.right);
        if( numright==k-1) return root.val;
        else if(numright>k-1) return kthLargest(root.right,k);
        else return kthLargest(root.left,k-numright-1);
    }
    private static int nodeNum(TreeNode root){
        if(root == null) return 0;
        else return 1+nodeNum(root.left)+nodeNum(root.right);
    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

思路：
递归。
执行用时：7 ms, 在所有 Java 提交中击败了42.56%的用户
内存消耗：41.2 MB, 在所有 Java 提交中击败了100.00%的用户

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        // 只在左边
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // 只在右边
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;   
    }
}