二叉树的遍历-前、中、后(递归与非递归)

非递归遍历

前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

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

//使用栈，把root结点放进去
//之后每次先push右子树、然后push左子树，每次把栈顶元素的值存到vector结果中

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        
        if(root==nullptr)
            return res;
        
        stack<TreeNode*> sta;
        TreeNode* curr = root;
        while(curr!=nullptr || !sta.empty()){
            while(curr!=nullptr){
                sta.push(curr);
                curr = curr->left; //一直遍历左子树
            }
            TreeNode* tmp = sta.top();
            sta.pop();
            res.push_back(tmp->val); //每次仍然是从栈顶读取要存储的元素
            curr = tmp->right;
            
        }
  
        return res;
    } 
    
};

后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr)
            return res;
        
        stack<TreeNode*> sta;
        TreeNode* curr = root;
        TreeNode* pre = nullptr;
            
        while(curr!=nullptr || !sta.empty()){
            while(curr!=nullptr){
                sta.push(curr);
                curr = curr->left;  //此部分同中序一样，同样要先遍历左结点
            }
            
            TreeNode* tmp = sta.top();
            if(tmp->right==nullptr || pre==tmp->right){ //没有左子树，或者右子树已经遍历过。则push当前跟结点
                sta.pop();
                res.push_back(tmp->val);
                pre = tmp;
                curr = nullptr;   
            }else{
                curr = tmp->right;
                pre = nullptr;   
            }
        }
        
        
        return res;
    }
    
};

递归遍历

递归遍历的规律：无论何时push_back的都是当前的跟结点，遇到左右结点，都是继续递归遍历。

前序遍历

 1 class Solution {
 2 public:
 3     vector<int> preorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         preorderTraversalCore( root, res); 
 6         return res;
 7     }
 8     
 9     void preorderTraversalCore(TreeNode* root,vector<int>& res){
10         if(root==nullptr)
11             return;
12         res.push_back(root->val);
13         preorderTraversalCore( root->left, res); 
14         preorderTraversalCore( root->right, res); 
15         return;
16     }
17 };

preOrder

中序遍历

 1 class Solution {
 2 public:
 3     vector<int> inorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         inorderTraversalCore( root, res); 
 6         return res;
 7     }
 8     
 9     void inorderTraversalCore(TreeNode* root,vector<int>& res){
10         if(root==nullptr)
11             return;
12         inorderTraversalCore( root->left, res); 
13         res.push_back(root->val);
14         inorderTraversalCore( root->right, res); 
15         return;
16     }   
17     
18 };

inorder

后序遍历

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode* root) {
 4         vector<int> res;
 5         postorderTraversalCore( root, res); 
 6         return res;
 7     }
 8     
 9     void postorderTraversalCore(TreeNode* root,vector<int>& res){
10         if(root==nullptr)
11             return;
12         postorderTraversalCore( root->left, res); 
13         postorderTraversalCore( root->right, res); 
14         res.push_back(root->val);
15         return;
16     }
17     
18 };

View Code