树的深度优先遍历

1 前言

前段时间了解到可以用队列实现树的广度优先遍历后，在 LeetCode 刷题的时候，又发现可以用栈来实现 树的深度优先遍历.

这是一个值得思考的发现！

2 树类型

考虑到之后的内容会用到这两个树类型，就先在这里把它们列出来好了：

// 二叉树
public class BinaryTree {
  public int val;
  public BinaryTree left;
  public BinaryTree right;

  public BinaryTree(int val) {
    this.val = val;
  }
}

// 多叉树
public class GenericTree {
  public int val;
  public List<GenericTree> children;

  public GenericTree(int val) {
    this.val = val;
    this.children = new ArrayList<GenericTree>();
  }
}

3 使用递归的深度优先遍历

使用递归实现树的深度优先遍历实在是太简单了，随便一本教材都会讲到这一实现，就不多说了，直接上代码：

public class RecursiveTraversal {
  public static void traversal(BinaryTree root) {
    if (root == null) {
      return;
    }

    traversal(root.left);
    traversal(root.right);

    visit(root);
  }

  public static void traversal(GenericTree root) {
    if (root == null) {
      return;
    }

    for (GenericTree child : root.children) {
      traversal(child);
    }

    visit(root);
  }

  public static void visit(BinaryTree node) {
    // 访问处理节点
  }

  public static void visit(GenericTree node) {
    // 访问处理节点
  }
}

NOTE: 这里的实现只考虑先访问叶子节点，在访问父节点的遍历类型，对于二叉树来说，对应的就是 后序遍历.

4 使用栈的深度优先遍历

使用栈实现树的深度优先遍历的基本思路是利用栈 后进先出 的特性，将父节点保存到栈中，出栈时的节点优先为子节点。

当然，还有一个隐含的条件为：得到的节点是树的根结点。

首先是使用栈实现二叉树的深度优先遍历：

public class StackTraversal {
  public static void traversal(BinaryTree root) {
    Deque<BinaryTree> stack = new ArrayDeque<BinaryTree>();
    BinaryTree lastVisited = null;  // 最后一个访问 visit 的节点

    while (!stack.isEmpty() || root != null) {
      if (root != null) {
        stack.addFirst(root);
        root = root.left;
      } else {
        BinaryTree peekNode = stack.peekFirst();
        if (peekNode.right != null && lastVisited != peekNode.right) {  // 判断该节点的右子节点是否已访问
          root = peekNode.right;
        } else {
          visit(peekNode);
          lastVisited = stack.removeFirst();
        }
      }
    }
  }

  public static void visit(BinaryTree node) {
    // 访问处理节点
  }
}

这里实现的依旧是二叉树的 后序遍历, 实现难度是三种遍历方式中最大的，所以直接看代码可能不太容易理解。

算法可视化的工具也没找到合适的，就先将就着看吧 @_@

然后是使用栈实现多叉树的深度优先遍历：

public class StackTraversal {
  public static void traversal(GenericTree root) {
    if (root == null) {
      return;
    }

    Deque<BinaryTree> stack = new ArrayDeque<BinaryTree>();
    BinaryTree lastVisited = null;

    stack.addFirst(root);

    while (!stack.isEmpty()) {
      BinaryTree peekNode = stack.peekFirst();

      if (peekNode.children.size() != 0 && lastVisited != peekNode.children.get(0)) {  // 判断该节点的子节点是否已访问
        for (GenericTree child : peekNode.children) {
          stack.addFirst(child);
        }
      } else {
        visit(peekNode);
        lastVisited = stack.removeFirst();
      }
    }
  }

  public static void visit(GenericTree node) {
    // 访问处理节点
  }
}

道理和二叉树的差不多，但感觉应该比二叉树的容易理解些。

NOTE: 栈是用双端队列近似模拟的，这也是 JDK 推荐的方式。

5 使用栈的深度优先遍历 · 补

想了一下，决定还是补一份使用栈实现二叉树的先序遍历和中序遍历的代码：

public static void preOrder(BinaryTree root) {
  if (root == null) {
    return;
  }

  Deque<BinaryTree> stack = new ArrayDeque<BinaryTree>();

  stack.addFirst(root);

  while (!stack.isEmpty()) {
    BinaryTree node = stack.removeFirst();

    visit(node);

    if (node.right != null) {  // 栈是后进先出的
      stack.addFirst(node.right);
    }

    if (node.left != null) {
      stack.addFirst(node.left);
    }
  }
}

public static void inOrder(BinaryTree root) {
  Deque<BinaryTree> stack = new ArrayDeque<BinaryTree>();

  while (!stack.isEmpty() || root != null) {
    if (root != null) {
      stack.addFirst(root);
      root = root.left;
    } else {
      root = stack.removeFirst();
      visit(root);
      root = root.right;
    }
  }
}

总感觉代码写的有点丑 @_@

6 结语

通过栈来实现 树的深度优先遍历 并不是很难，更重要的地方在于用栈来代替递归的想法。

最近学习 编译原理 的过程中，语法分析部分提到过：递归调用的方式会隐式地维护一个栈，某些情况下，可以通过显式地维护一个栈来消除递归。

递归下降预测分析器到非递归预测下降分析器就是通过这样的方式实现的。

递归和栈孰优孰劣先不讨论，通过栈消除递归的做法还是很有启发性的，值得学习！

7 参考链接

Tree traversal - wiki