树的遍历

二叉树的遍历

二叉树的遍历操作复杂度，跟节点的个数n成正比，也就是说二叉树遍历的时间复杂度是O(n)。

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

二叉树本身是递归定义的，相应的遍历很自然就成为一种递归问题。

写递归代码的关键，就是看能不能写出递推公式，而写递推公式的关键就是，如果解决问题A，就假设子问题B、C已经解决，然后再来看如何利用B、C来解决A。所以可以把前、中、后序遍历的递推公式都写出来。

//前序遍历的递推公式：
preorder(r) = print r -> preorder(r.left) -> preorder(r.right)

//中序遍历的递推公式：
inorder(r) = inorder(r.left) -> print r -> inorder(r.right)

//后序遍历的递推公式：
postorder(r) = postorder(r.left) -> postorder(r.right) -> print r

递归遍历操作的关键点是递归体和递归出口：

• 递归出口是二叉树的空子树或叶节点，此时为空操作，递归不继续进行，只能回退；
• 递归体是对二叉树根节点或左、右子树进行相应处理。

基于递归的遍历算法易于编写，操作简单，但可读性差，系统需要维护相应的工作栈，效率不是很高。

递归转化为非递归的基本思想是如何实现原本是系统完成的递归工作栈，为此，可以仿照递归执行过程中工作栈状态变化而得到。

对二叉树进行前序、中序和后序遍历时都开始于根节点或结束于根节点，经由路线也相同。彼此差别在于对节点访问时机的选择不同。三种遍历方式都是沿着左子树不断深入下去，当到达二叉树左下节点而无法往下深入时，就向上逐一返回，行进到最近深入时曾遇到节点的右子树，然后进行同样的深入和返回，直到最终从根节点的右子树返回到根节点。
这样，遍历时返回顺序与深入节点顺序恰好相反，因此可以在实现二叉树遍历过程中，使用一个工作栈来保存当前深入到的节点信息，以供后面返回需要时使用。

树的节点的定义：

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

中序遍历(inorder traversal)

递归遍历

二叉树分为根节点、左子树和右子树，分别表示为 +、1、2。
遍历顺序为： 1+2 可以递增顺序显示BST中所有节点。

• 中序遍历访问左子二叉树
• 访问根节点
• 中序遍历访问右子二叉树

中序遍历递归方法

public void inorder() {
    inorder(root);      
}

protected void inorder(TreeNode root) {
    if (root == null)
        return;
    inorder(root.left);  // 递归遍历左子树
    System.out.print(root.val + " ");  // 递归遍历根节点
    inorder(root.right);  // 递归遍历右子树 1+2
}

非递归遍历

中序遍历的黄金口诀：当前节点(current=root)不为空，压栈，当前节点向左移动；当前节点为空，从栈中弹出一个元素，并打印该节点，当前节点向右移动；

中序遍历非递归方法

public void inorder() {
    inorder(root);
}

protected void inorder(TreeNode root) {
    if (root == null) 
        return;
    java.util.Stack<TreeNode> stack = new java.util.Stack<>();
    TreeNode current = root;
    while (!stack.empty() || current != null) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {            
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            current = node.right;
        }
    }
}

前序遍历(preorder traversal)

递归遍历

+12 深度优先遍历法(depth-first traversal)与前序遍历法相同。

• 访问根节点
• 前序遍历访问左子二叉树
• 前序遍历访问右子二叉树

preorder递归遍历

public void preorder() {
    preorder(root);
}
protected void preorder(TreeNode root) {
    if (root == null)
        return;
    System.out.println(root.val + " ");  // 递归遍历根节点
    preorder(root.left);  // 递归遍历左子树
    preorder(root.right);  // 递归遍历右子树 +12
}

非递归遍历

根节点入栈，栈不为空，则循环：出栈并打印节点值，右孩子节点进栈，左孩子节点进栈。

前序非递归遍历

public void preorder() {
    preorder(root);
}    
protected void preorder(TreeNode root) {
    if (root == null) 
        return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.empty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");

        // Push the right child onto the stack 
        // first so the left is processed first
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

后序遍历(postorder traversal)

递归遍历

1 2 +

• 后序遍历访问左子二叉树
• 后序遍历访问右子二叉树
• 访问根节点

postorder递归遍历

public void postorder() {
    postorder(root);
}
protected void postorder(TreeNode root) {
    if (root == null)
        return;
    postorder(root.left);  // 递归遍历左子树
    postorder(root.right);  // 递归遍历右子树
    System.out.println(root.val + " ");  // 递归遍历根节点 12+
}

非递归遍历

需要两个栈，一个栈用来模拟后续遍历顺序，另一个栈用来存储后续遍历打印顺序。

根节点入栈1，栈1不为空则循环：栈1出栈，将出栈元素存到栈2，出栈节点左孩子节点进栈，右孩子节点进栈； 打印栈2的元素

后序非递归遍历

public void postorder() {
    postorder(root);
}

protected void postorder(TreeNode root) {
    if (root == null) return;

    // Create two stacks
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();

    // push root to stack1
    stack1.push(root);
    while (!stack1.empty()) {
        // Pop node from stack1 and push onto stack2
        TreeNode node = stack1.pop();
        stack2.push(node);

        if (node.left != null)
            stack1.push(node.left);
        if (node.right != null)
            stack1.push(node.right);
    }

    // Display vals in stack2
    while (!stack2.empty()) {
        System.out.print(stack2.pop().val + " ");
    }
}

广度优先遍历(breadth-first traversal)

根节点先入队，然后队列不空，取出对头元素，如果左孩子存在就入队列，否则什么也不做，右孩子同理。知道队列为空，则表示树层次遍历结束。树的层次遍历，其实也是广度优先的遍历算法。

广度优先遍历

public void breadthFirstTraversal() {
    if (root == null)
        return;

    // Queue Deque Linkedlist
    Queue<TreeNode> queue = new LinkedList<>();  

    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.element();
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
        System.out.println(queue.remove().val + " ");
    }
}

---