二叉搜索树|不同、验证、转换等

二叉搜索树|不同、验证、转换等

96 不同的二叉搜索树

• 参考力扣官方题解，链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
• G(n) = sum(G(i-1)·G(n-i))
• G(2)=G(0)·G(1)+G(1)·G(0)
• G(3)=G(0)·G(2)+G(1)·G(1)+G(2)·G(0)

/**
 * 不同的二叉搜索树
 * 参考力扣官方题解，链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
 * G(n) = sum(G(i-1)·G(n-i))
 * G(2)=G(0)·G(1)+G(1)·G(0)
 * G(3)=G(0)·G(2)+G(1)·G(1)+G(2)·G(0)
 */
public class $96 {
    public int numTrees(int n) {
        int[] G = new int[n+1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                G[i] += G[j-1] * G[i-j];
                // System.out.println("G  " + i + " " + j + " " + (j-1) + " " + (i-j));
            }
        }
        return G[n];
    }
}

98 验证二叉搜索树

• 法一：递归
• 法二：中序遍历得到的结果是升序的

import java.util.Stack;

/**
 * 验证二叉搜索树
 * 法一：递归
 * 法二：中序遍历得到的结果是升序的
 */
public class $98 {
    //法一：递归
    public boolean isValidBST(TreeNode root) {
        return process(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean process(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }

        if (node.val <= lower || node.val >= upper) {
            return false;
        }

        return process(node.left, lower, node.val) && process(node.right, node.val, upper);
    }
}

import java.util.Stack;

/**
 * 验证二叉搜索树
 * 法一：递归
 * 法二：中序遍历得到的结果是升序的
 */
public class $98 {
    //法二；中序遍历得到的结果是升序的
    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        double prev =  -Double.MAX_VALUE;
        while (true) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            TreeNode tmp = stack.pop();
            if (tmp.val <= prev) return false;
            prev = tmp.val;
            cur = tmp.right;
        }
        return true;
    }
}

538 把二叉搜索树转换为累加树

• 法一：递归，右中左遍历
• 法二：morris反序中序遍历

/**
 * 把二叉搜索树转换为累加树
 * 法一：递归，右中左遍历
 * 法二：morris反序中序遍历
 */
public class $538 {
    //法一：递归，右中左遍历
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}

/**
 * 把二叉搜索树转换为累加树
 * 法一：递归，右中左遍历
 * 法二：morris反序中序遍历
 */
public class $538 {
    //法二：morris反序中序遍历
    public TreeNode convertBST2(TreeNode root) {
        int sum = 0;
        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null) {
            prev = cur.right;

            if (prev != null) {
                while (prev.left != null && prev.left != cur) {
                    prev = prev.left;
                }

                if (prev.left == null) {
                    prev.left = cur;
                    cur = cur.right;
                } else {
                    prev.left = null;
                    sum += cur.val;
                    cur.val = sum;
                    cur = cur.left;
                }
            } else {
                sum += cur.val;
                cur.val = sum;
                cur = cur.left;
            }
        }
        return root;
    }

}