二叉树的各种遍历

1. 先序/后序/中序遍历

递归版本的就不谈了，主要看非递归版本。

首先定义一个术语 左路径，它指的是从某个节点开始（包括该节点），沿着左孩子向下走直到叶子节点，所形成的路径。

3个顺序的遍历都遵循以下代码框架：

Node root = ... ;

while(root != null){        // 1. 用以 root 为起点的左路径初始化栈
    stack.push(root);
    root = root.left;
}

while(stack不为空){         // 当栈不为空，循环：
    Node n = stack.pop();   // 2. 从栈中 pop 一个节点出来

    Node tmp = n.right;     // 3. 将该节点 *右孩子* 的左路径入栈
    while(tmp != null){
        stack.push(tmp);
        tmp = tmp.left;
    }
}

简单来说就是下面两步：

  1. 用根的左路径初始化栈；
  2. 循环从栈中 pop 节点，并将该节点右孩子的左路径入栈

其实就是 深度优先遍历 的思路，只在一些细节地方不同。是不是很简单呢？

先序和中序

先序遍历的过程中，每个节点的访问时机是在节点 入栈 时，因此对上述代码框架，在两处 push 处加上对节点的访问逻辑即可。

Stack<TreeNode> s = new Stack<TreeNode>();

while(root != null){
    visit(root);    // <-- 1 visit when push
    s.push(root);
    root = root.left;
}

while(!s.isEmpty()){
    TreeNode tmp = s.pop();

    tmp = tmp.right;
    while(tmp != null){
        visit(tmp); // <-- 2 visit when push
        s.push(tmp);
        tmp = tmp.left;
    }
}

对于中序，每个节点的访问时机是在节点 出栈 时，因此应当在 while 循环内每次 pop 时对节点进行访问。

Stack<TreeNode> s = new Stack<TreeNode>();

while(root != null){
    s.push(root);
    root = root.left;
}

while(!s.isEmpty()){
    TreeNode tmp = s.pop();
    visit(tmp);  // <-- visit when pop

    tmp = tmp.right;
    while(tmp != null){
        s.push(tmp);
        tmp = tmp.left;
    }
}

后序

后序稍微复杂一些，当一个节点从 stack pop 出来时，意味着 它的左子树已经访问完毕 了，先序和中序此时都可以直接去处理它的右子树；但是后序遍历要求访问完它的右子树后，再访问该节点。

因此对于后序遍历，节点第一次出栈时，必须将其重新入栈，再走后续流程（将右孩子的左路径入栈）；当节点第二次出栈，说明 它的右子树也访问完了，这时才可以访问该节点。所以，对每个节点都必须用一个额外的标志位，记录它是初次还是第二次出栈。

代码如下：

Stack<TreeNode> s = new Stack<TreeNode>();

while(root != null){
    s.push(root);
    root = root.left;
}

while(!s.isEmpty()){
    TreeNode tmp = s.pop();

    if(tmp.poped){          // 1. 如果是第二次出栈，访问它
        visit(tmp);
    }else{
        tmp.poped = true;   // 2. 如果是第一次出栈，标记并重新入栈
        s.push(tmp);

        tmp = tmp.right;
        while(tmp != null){
            s.push(tmp);
            tmp = tmp.left;
        }
    }
}

2. 层序遍历

基本的层序遍历用一个队列，循环出队并将其左右孩子依次入队，比较简单。

如果要区分每一行，则可以用一个标记节点标记一行的结束。遍历的过程中，如果出队的是标记节点，说明已经访问完了一行；此外也意味着这一行的孩子都已入队，标记节点应当重新入队。队列为空时遍历完成。

TreeNode mark = new TreeNode(0);        // 行末标记

LinkedList<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
q.add(mark);

List<Integer> row = new LinkedList<Integer>();
List<List<Integer>> rows = new LinkedList<List<Integer>> ();

while(!q.isEmpty()){
    TreeNode n = q.removeFirst();

    if(n == mark){                  // 碰到行末标记了
        rows.add(row);              // 说明访问完了一行
        if(q.isEmpty()) break;      // 队列为空则遍历完成
        q.add(mark);                // 这一行的全部孩子也已入队，将标记节点重新入队
        row = new LinkedList<Integer>();
    }else{
        row.add(n.val);
        if(n.left != null) q.add(n.left);
        if(n.right != null) q.add(n.right);
    }
}
Loading Disqus comments...
目录