二叉树

二叉树的遍历（非递归）

  • 前序遍历
    基本思路是把根节点入栈，然后出栈并访问，接着把右子节点入栈，最后把左子节点入栈。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void preOrderIterative(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " "); // 访问根节点
            if (node.right != null) stack.push(node.right); // 右子节点先入栈
            if (node.left != null) stack.push(node.left);   // 左子节点后入栈
        }
    }

  • 中序遍历
    基本思路就是从根开始把左子节点都入栈，当没有左子节点时，出栈并访问右子节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public void inOrderIterative(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {            // 左子节点依次入栈
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();               // 访问栈顶节点
            System.out.print(curr.val + " ");
            curr = curr.right;                // 转向右子树
        }
    }

  • 后序遍历
    后序遍历的顺序是左右根，而前序遍历的顺序是根左右，所以可以先按照根右左的顺序遍历，然后再逆序输出。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public void postOrderIterative(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> output = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.push(node);                // 根节点先入辅助栈
            if (node.left != null) stack.push(node.left);   // 左子节点入栈
            if (node.right != null) stack.push(node.right); // 右子节点入栈
        }
        while (!output.isEmpty()) {
            System.out.print(output.pop().val + " ");       // 按后序输出
        }
    }

  • 层序遍历
    层级遍历需要借助队列，先把根节点入队，然后出队并访问，接着把左右子节点入队。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " "); // 访问节点
            if (node.left != null) queue.offer(node.left);  // 左子节点入队
            if (node.right != null) queue.offer(node.right); // 右子节点入队
        }
    }

做了一道leecode102题，也是层序遍历，但是要返回的是[[3],[9,20],[15,7]]这种把每一层的点再包在一个list中的形式。
这个时候就需要在每一层遍历的时候，记录下当前层的节点个数（也就是此时队列的长度），然后再遍历这个个数的节点，把他们的值加入到一个list中，最后再把这个list加入到结果中。

二叉搜索树（BST）

二叉搜索树是一种特殊的二叉树，对于每个节点，其左子树上的所有节点的值都小于根节点的值，右子树上的所有节点的值都大于根节点的值。

leecode98题验证二叉搜索树，我太想当然把二叉搜索树当成左孩子小于当前节点，右孩子大于当前节点了。。
应该是左子树的所有节点值都必须小于当前节点值，而右子树的所有节点值都必须大于当前节点值。在调用递归的时候应该判断的是左节点和右节点在一个区域low和high之间。对于左节点，应该更新他的最大值high为当前节点的值，而对于右节点，应该更新他的最小值low为当前节点的值。

还有一种办法是用中序遍历的方式。根据二叉搜索树的性质可知，二叉搜索树中序遍历得到的值构成的序列一定是升序的。所以我们可以在中序遍历的时候检查当前节点的值是否大于前一个中序遍历的节点的值即可。

leecode96题不同的二叉搜索树。这道题是求1到n这n个数能组成多少种不同的二叉搜索树。这道题的思路是，对于每个节点i，以i为根节点的二叉搜索树的数量是左子树的数量乘以右子树的数量。
所以可以用动态规划的方法，dp[i]表示1到i这i个数能组成的不同二叉搜索树的数量。对于每个i，我们可以把1到i中的每个数都作为根节点，然后分别计算左子树和右子树的数量，然后相乘即可。

1
2
3
4
5
6
7
8
9
10
11
12
public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i < G.length; i++) {
            for (int j = 1; j <= i; j++) {
                G[i] += G[j - 1] * G[i - j];
            }
        }

        return G[n];
    }

动态规划的核心思想是将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。动态规划的实现通常是自底向上的，即先解决子问题，再逐步解决原问题。

leecode95题是按任意顺序返回二叉搜索树，不想做。。有时间记得看看。。