Binary Tree Depth Order Traversal

前面我们解决了tree的level order遍历问题，这里我们需要来处理tree的depth order，也就是前序，中序和后序遍历。

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

给定一颗二叉树，使用迭代的方式进行前序遍历。

因为不能递归，所以我们只能使用stack来保存迭代状态。

对于前序遍历，根节点是最先访问的，然后是左子树，最后才是右子树。当访问到根节点的时候，我们需要将右子树压栈，这样访问左子树之后，才能正确地找到对应的右子树。

代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode *root) {
  4.         vector<int> vals;
  5.         if(root == NULL) {
  6.             return vals;
  7.         }
  9.         vector<TreeNode*> nodes;
  11.         //首先将root压栈
  12.         nodes.push_back(root);
  14.         while(!nodes.empty()) {
  15.             TreeNode* n = nodes.back();
  16.             vals.push_back(n->val);
  18.             //访问了该节点，出栈
  19.             nodes.pop_back();
  21.             //如果有右子树，压栈保存
  22.             if(n->right) {
  23.                 nodes.push_back(n->right);
  24.             }
  26.             //如果有左子树，压栈保存
  27.             if(n->left) {
  28.                 nodes.push_back(n->left);
  29.             }
  30.         }
  32.         return vals;
  33.     }
  34. };

Binary Tree Inorder Traversal

给定一颗二叉树，使用迭代的方式进行中序遍历。

对于中序遍历，首先遍历左子树，然后是根节点，最后才是右子树，所以我们需要用stack记录每次遍历的根节点，当左子树遍历完成之后，从stack弹出根节点，得到其右子树，开始新的遍历。

代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> inorderTraversal(TreeNode *root) {
  4.         vector<int> vals;
  5.         if(root == NULL) {
  6.             return vals;
  7.         }
  9.         vector<TreeNode*> nodes;
  10.         TreeNode* p = root;
  11.         while(p || !nodes.empty()) {
  12.             //这里一直遍历左子树，将根节点压栈
  13.             while(p) {
  14.                 nodes.push_back(p);
  15.                 p = p->left;
  16.             }
  18.             if(!nodes.empty()) {
  19.                 p = nodes.back();
  20.                 vals.push_back(p->val);
  22.                 //将根节点弹出，获取右子树
  23.                 nodes.pop_back();
  24.                 p = p->right;
  25.             }
  26.         }
  28.         return vals;
  29.     }
  30. };

Binary Tree Postorder Traversal

给定一颗二叉树，使用迭代的方式进行后序遍历。

对于后序遍历，首先遍历左子树，然后是右子树，最后才是根节点。当遍历到一个节点的时候，首先我们将右子树压栈，然后将左子树压栈。这里需要注意一下出栈的规则，对于叶子节点来说，直接可以出栈，但是对于根节点来说，我们需要一个变量记录上一次出栈的节点，如果上一次出栈的节点是该根节点的左子树或者右子树，那么该根节点可以出栈，否则这个根节点是新访问的节点，将右和左子树分别压栈。

代码如下：

  1. class Solution {
  2. public:
  3.     vector<int> postorderTraversal(TreeNode *root) {
  4.         vector<int> vals;
  5.         if(root == NULL) {
  6.             return vals;
  7.         }
  9.         vector<TreeNode*> nodes;
  10.         TreeNode* pre = NULL;
  12.         nodes.push_back(root);
  14.         while(!nodes.empty()) {
  15.             TreeNode* p = nodes.back();
  16.             //如果不判断pre，我们就没法正确地出栈了
  17.             if((p->left == NULL && p->right == NULL) ||
  18.                 (pre != NULL && (pre == p->left || pre == p->right))) {
  19.                 vals.push_back(p->val);
  20.                 nodes.pop_back();
  21.                 pre = p;
  22.             } else {
  23.                 //右子树压栈
  24.                 if(p->right != NULL) {
  25.                     nodes.push_back(p->right);
  26.                 }
  28.                 //左子树压栈
  29.                 if(p->left != NULL) {
  30.                     nodes.push_back(p->left);
  31.                 }
  32.             }
  33.         }
  35.         return vals;
  36.     }
  37. };

总结

可以看到，树的遍历通过递归或者堆栈的方式都是比较容易的，网上还有更牛的不用栈的方法，只是我没理解，就不做过多说明了。