二叉树遍历

[Jessie-Cheng1]

二叉树的结构定义：

struct Treenode{
  int val;
  Treenode* left;
  Treenode* right;
  Treenode(int x,Treenode* left,Treenode* right){val(x), left(left), right(right) 
};

深度

1. 递归

• 前

  class Solution {
  public:
  vector<int> res;
  vector<int> preorderTraversal(TreeNode* root) {
      if(root==nullptr) return res;
      res.push_back(root->val);
      preorderTraversal(root->left);
      preorderTraversal(root->right);
      return res;
  }
  };

• 中

  class Solution {
  public:
  vector<int> res;
  vector<int> inorderTraversal(TreeNode* root) {
      if(root==nullptr) return res;
      inorderTraversal(root->left);
      res.push_back(root->val);
      inorderTraversal(root->right);
      return res;
  }
  };

• 后

  class Solution {
  public:
  vector<int> res;
  vector<int> postorderTraversal(TreeNode* root) {
      if(root==nullptr) return res;
      postorderTraversal(root->left);
      postorderTraversal(root->right);
      res.push_back(root->val);
      return res;
  }
  };

2. 迭代 用栈来实现，栈是先进后出的结构
   • 前 根先压入，然后弹出根 接下来栈压入右子树、左子树，所以出来就是左、右 所以就是根左右

     class Solution {
     public:
     vector<int> preorderTraversal(TreeNode* root) {
     stack<TreeNode*> st;
     vector<int> res;
     if(root) st.push(root);
     while(!st.empty()){
         TreeNode* node=st.top();
         st.pop();
         res.push_back(node->val);
         if(node->right) st.push(node->right);//注意顺序，栈是先进后出
         if(node->left) st.push(node->left);//这里要加if判断，递归不用，因为递归进去之后会有判断是不是为空
     }
     return res;
     }
     }; 

   • 中 和前后有点不一样，因为它的处理顺序和访问顺序是不一致的。 所以需要用指针的遍历指向访问的结点，栈用来处理结点上的元素。

     class Solution {
     public:
     vector<int> inorderTraversal(TreeNode* root) {
     stack<TreeNode*> st;
     vector<int> res;
     TreeNode* cur=root;
     while(cur!=nullptr || !st.empty()){
         if(cur!=nullptr){
             st.push(cur);
             cur=cur->left;
         }
         else{
             cur=st.top();
             st.pop();
             res.push_back(cur->val);
             cur=cur->right;
         }
     }
     return res;
     }
     };

• 后 根先压入栈，然后弹出压到vector 然后压入栈左子树、右子树，所以出来就是根右左 再反转vector，所以就是左右根

  class Solution {
  public:
  vector<int> postorderTraversal(TreeNode* root) {
      stack<TreeNode*> st;
      vector<int> res;
      if(root) st.push(root);
      while(!st.empty()){
          TreeNode* node=st.top();
          st.pop();
          res.push_back(node->val);
          if(node->left) st.push(node->left);
          if(node->right) st.push(node->right);
  
      }
      reverse(res.begin(),res.end());
      return res;
  }
  };

广度（层次）