二叉查找树

判断序列是否为BST的后序遍历

在二叉查找树中插入节点

利用中序遍历，解决问题：找到BST中的第k个元素（从小到大）、验证BST

验证二叉查找树

二叉查找树迭代器

判断序列是否为BST的后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果

// 递归判断
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null || sequence.length==0){
            return false;
        }
        
        int len = sequence.length;
        int root = sequence[len-1];
        
        // 找到比root大的第一个节点，这个节点属于root的右子树
        int i=0;
        for(i=0; i<len-1; i++){
            if(sequence[i]>root){
                break;
            }
        }
        
        int j=i;
        for(j=i; j<len-1; j++){ // root节点的右子树，都应该比root大
            if(sequence[j]<root){ // 如果存在比root小的，return false
                return false; 
            }
        }
        
        boolean left=true;
        boolean right=true;        
        if(i>0){
            left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
        }
        if(i<len-1){
            right=VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, len-1));            
        }
        
        return left&&right;
    }
}

在二叉查找树中插入节点

递归

public TreeNode insertNode(TreeNode root, TreeNode node) {
    if (root == null) {
        return node;
    }
    if (root.val >= node.val) {
        root.left = insertNode(root.left, node);
    }
    if (root.val < node.val) {
        root.right = insertNode(root.right, node);
    }
    return root;
}

 非递归

public TreeNode insertNode(TreeNode root, TreeNode node) {
    if (root == null) {
        return node;
    }

    TreeNode cur = root;
    TreeNode last = null;

    while (cur != null) {
        last = cur;
        if (cur.val > node.val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }

    if (last != null) {
        if (last.val > node.val) {
            last.left = node;
        } else {
            last.right = node;
        }
    }
    return root;
}

利用中序遍历，解决问题：找到BST中的第k个元素（从小到大）、验证BST

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;

    }
    return list;
}

找到BST中的第k个元素（从小到大）

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    while(root!=null || !stack.isEmpty()){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if(--k==0){
            break;
        }
        root = root.right;
    }
    return root.val;
}

验证二叉查找树

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

• 节点的左子树中的值要严格小于该节点的值。
• 节点的右子树中的值要严格大于该节点的值。
• 左右子树也必须是二叉查找树。
• 一个节点的树也是二叉查找树。

解法一：inorder（递归）二叉树，得到list，再遍历这个list比较是否为BST

解法二：inorder（迭代）二叉树，并对每次迭代判断！

public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    while(root!=null || !stack.isEmpty()){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if(prev!=null && prev.val>=root.val){
            return false;
        }
        prev = root;
        root = root.right;
    }
    return true;
}

 解法三：递归

public class Solution {
    private TreeNode prev = null;

    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)) return false;
        if(prev != null && root.val <= prev.val) return false;
        prev = root;
        return isValidBST(root.right);
    }
}

 二叉查找树迭代器

Calling next() will return the next smallest number in the BST.

public class BSTIterator {
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeft(root);
    }
    
    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }
}