数据结构

二叉树数据结构如下：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

1 二叉树的遍历

二叉树是一种非常常用的数据结构，也是面试的热门词。而二叉树最常见的考点莫过于遍历，下面将介绍二叉树的几种遍历方式，包括遍历的递归与非递归实现。

遍历方式比较：

1.1 前序遍历

1. 遍历过程

递归：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。 非递归：可以使用一个栈来模拟这种操作。（利用回溯思想） 若二叉树为空，则空操作返回， 当根节点（root）与栈（stack）同时不为空，判断 root 是否为空， 不为空：输出 root.val，将 root 压栈，并将 root 指向 root.left 为空：让 root 指向 stack.pop() ，并将 root 指向 root.right

2. 代码实现

import java.util.Stack;

public class TreePreOrder {
    // 前序递归遍历
    public static void preOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        System.out.print(tree.val + "\t");
        preOrderRecursively(tree.left);
        preOrderRecursively(tree.right);
    }

    // 前序非递归遍历
    public static void preOrderIteratively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        TreeNode root = tree;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                System.out.print(root.val + "\t");
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop().right;
            }
        }
        System.out.println();
    }
}

1.2 中序遍历

1. 遍历过程

• 递归：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点左子树，然后访问根结点，最后中序遍历右子树。
• 非递归：可以使用一个栈来模拟这种操作。（利用回溯思想）
  • 若二叉树为空，则空操作返回，
  • 当根节点（root）与栈（stack）同时不为空，判断 root 是否为空，
    • 不为空：将root压栈，并将 root 指向其左孩子节点 root.left
    • 为空：输出栈顶节点值（stack.peek().val），让 root 指向 stack.pop()，并将 root 重新指向 root.right

2. 代码实现

import java.util.Stack;

public class TreeInOrder {
    // 中序递归遍历
    public static void inOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        inOrderRecursively(tree.left);
        System.out.print(tree.val + "\t");
        inOrderRecursively(tree.right);
    }

    // 中序非递归遍历
    public static void inOrderIteratively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        TreeNode root = tree;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                System.out.print(stack.peek().val + "\t");
                root = stack.pop().right;
            }
        }
        System.out.println();
    }
}

1.3 后序遍历

1. 遍历过程

• 递归：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
• 非递归：可以使用一个栈（stack）和上一个访问节点（prevVisted）来模拟这种操作。（利用回溯思想）
  • 若二叉树为空，则空操作返回，
  • 当根节点（root）与 stack 同时不为空，判断 root 是否为空，
  • 不为空：将 root 压栈，并将 root 指向 root.left
  • 为空：让 root 指向 stack.peek().right（栈顶节点的右节点），判断 root 是否为空以及是否等于 prevVisted
    • 若root 不为空 且 不等于 prevVisted：将 root 压栈，并将 root 指向 root.left
    • 否则：prevVisted 指向 stack.pop()，输出该节点值 prevVisted.val，root 指向nul

2. 代码实现

import java.util.Stack;

public class TreePostOrder {
    // 后序递归遍历
    public static void postOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        postOrderRecursively(tree.left);
        postOrderRecursively(tree.right);
        System.out.print(tree.val + "\t");
    }

    // 后序非递归遍历
    public static void postOrderIteratively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        TreeNode root = tree;
        TreeNode prevVisted = null;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.peek().right;
                if (root != null && root != prevVisted) {
                    stack.push(root);
                    root = root.left;
                } else {
                    prevVisted = stack.pop();
                    System.out.print(prevVisted.val + "\t");
                    root = null;
                }
            }
        }
        System.out.println();
    }
}

1.4 层序遍历

1. 遍历过程：

• 顺序打印：若二叉树为空，则空操作返回，否则从树的第一层开始，也就是从根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
• 逐层打印：和顺序打印基本一样，但为了逐层打印，需要把每次加入队列的所有节点一起输出（利用循环，具体细节见代码）。

2. 代码实现

import java.util.Queue;

public class TreeLevelOrder {
    // 层次遍历并顺序打印（借助队列）
    public static void levelOrder1(TreeNode tree) {
        if (tree == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(tree);
        TreeNode temp = null;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.print(temp.val + "\t");
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        System.out.println();
    }

    // 层次遍历并逐层打印（借助队列）
    public static void levelOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = size - 1; i >= 0; i--) {
                TreeNode temp = (TreeNode) queue.poll();
                System.out.print(temp.val + "\t");
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            System.out.println();
        }
    }
}

1.5 小总结

我们可以得到两个二叉树遍历的性质：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；