二叉树的遍历

二叉树的遍历

二叉树的遍历包括先序遍历，中序遍历，后序遍历，层次遍历等等。本文对此进行整理。
 
二叉树结构定义如下：

//Definition for binary tree
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

1. 先序遍历
 
先序遍历就是先访问根节点，然后再先序遍历左子树，最后先序遍历右子树。先序遍历也就是深度优先搜索（DFS）。
 
先序遍历递归实现：

vector<int> preorderTraversal(TreeNode *root)
{
 vector<int> vals;
 preorderTraversal(root, vals);
 return vals;
}
void preorderTraversal(TreeNode *root, vector<int> &vals)
{
 if(root == NULL) return;
 vals.push_back(root->val);
 preorderTraversal(root->left, vals);
 preorderTraversal(root->right, vals);
}

先序遍历非递归实现：

vector<int> preorderTraversal(TreeNode * root)
{
 vector<int> vals;
 stack<TreeNode*> s;
 TreeNode * p = root;
 while(!s.empty() || p)
 {
  if(p == NULL)
  {
   while(!s.empty() && (p == s.top()->right || s.top()->right == NULL))
   { // 右子树已访问，出栈
    p = s.top();
    s.pop();
   }
   if(s.empty()) break;
   // 左子树已访问，右子树尚未访问，访问右子树
   p = s.top()->right;
  }
  else
  {
   vals.push_back(p->val);
   s.push(p);
   p = p->left;
  }
 }
 return vals;
}