剑指 Offer 33. 二叉搜索树的后序遍历序列 & 54. 二叉搜索树的第k大节点

33题目描述：

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

解析：

递归
二叉搜索树的特点是左子树的值<根节点<右子树的值;
而后续遍历的顺序是:左子节点→右子节点→根节点；

Java:

public boolean verifyPostorder(int[] postorder) {
        if(postorder == null || postorder.length == 0) {
            return true;
        }
        return process(postorder, 0, postorder.length - 1);
    }
    public boolean process(int[] postorder, int left, int right) {
        if(left >= right) {
            return true;
        }
        int i = right - 1;
        while(i >= left && postorder[i] > postorder[right]) {
            i--;
        }
        for(int k = left; k <= i; k++) {
            if(postorder[k] > postorder[right]) {
                return false;
            }
        }
        return process(postorder, left, i) && process(postorder, i + 1, right - 1);
    }

JavaScript:

var verifyPostorder = function(postorder) {
    if(postorder == null || postorder.length == 0) {
        return true;
    }
    return process(postorder, 0, postorder.length - 1);

    function process(postorder, left, right) {
        if(left >= right) {
            return true;
        }
        let i = right - 1;
        while(i >= left && postorder[i] > postorder[right]) {
            i--;
        }
        for(let k = left; k <= i; k++) {
            if(postorder[k] > postorder[right]) {
                return false;
            }
        }
        return process(postorder, left, i) && process(postorder, i + 1, right - 1);
    }
};

54题目描述：

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

解析：

中序遍历的倒 为 “右、根、左” 顺序

Java:

public int kthLargest(TreeNode root, int k) {
        int rightCount = count(root.right);
        if(rightCount + 1 == k) {
            return root.val;
        } else if(rightCount >= k) {
            return kthLargest(root.right, k);
        } else {
            return kthLargest(root.left, k - rightCount - 1);
        }
    }
    public int count(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }

JavaScript:

var kthLargest = function(root, k) {
    let rightCount = count(root.right);
    if(rightCount + 1 === k) {
        return root.val;
    } else if(rightCount >= k) {
        return kthLargest(root.right, k);
    } else {
        return kthLargest(root.left, k - rightCount - 1);
    }
    function count(root) {
        if(root === null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
};