二叉树的遍历大总结

TypeError: Cannot read properties of undefined (reading 'v')

1.三种深度优先遍历方式的区别

1.1 前序遍历（表明根节点在最前面遍历）

==遍历顺序：==根 左 右

1-2-4-5-3-6-7

1.1.1 递归遍历

递归格式如下：

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

1.1.2 迭代遍历(退一进二)

class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root){
        //定义一个容器，存放遍历结果
        vector<int> result;
        //定义一个辅助栈,存放节点
        stack<TreeNode*> st;
        
        if(root == nullptr) return result;
        //先放入根节点
        st.push(root);
        //退一进二
        while(!st.empty()){
            TreeNode* curNode= st.top();
            st.pop();
            result.push_back(curNode->val);
            //由于栈先进后出，因此先放右节点，再放左节点
            if(curNode->right) st.push(curNode->right);
            if(curNode->left) st.push(curNode->left);
        }
        return result;
    }
}

1.2 中序遍历（表明根节点在中间遍历）

遍历顺序： 左 根 右

4-2-5-1-6-3-7

1.2.1 递归遍历

递归格式如下：

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

1.2.2 迭代遍历（退一换右）

class Solution{
public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> result;
        stack<TreeNode*>st;
        if(root == nullptr) return ;
     	
        TreeNode* curNode = root; 
        while(curNode != nullptr || !st.empty()){
            
            while(curNode != nullptr){
                st.push(curNode);
                curNode = curNode -> left;
            }
            TreeNode* Node = st.top();
            st.pop();
            result.push_back(Node->val);
            //将curNode更新为当前节点的右子节点
            curNode = Node -> right;
        }
        return result;
    }
}

1.3 后序遍历（表明根节点在最后遍历）

遍历顺序： 左 右 根

4-5-2-6-7-3-1

1.3.1 递归遍历

递归格式如下：

class Solution{
public:
    void posorder(TreeNode* root,vector<int> &result){
        if(root == nullptr) return ;
        posorder(root->left,result);
        posorder(root->right,result);
        result.push_back(root->val);
    }
    vector<int> posorderTraversal(TreeNode* root){
        vector<int> result;
        posorder(root,result);
        return result;
    }
}

1.3.2 迭代遍历

后序遍历的顺序：左 右 根

前序遍历的顺序：根 左 右

因此将：根 右 左 反转就会变成：左 右 根

前序遍历时，由于栈是先进后出的，因此先存放的右节点，再存放的左节点，这里我们直接先存左节点，再存右节点，这样遍历的顺序就是：根 右 左，最后再反转就行。

class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root){
        //定义一个容器，存放遍历结果
        vector<int> result;
        //定义一个辅助栈,存放节点
        stack<TreeNode*> st;
        
        if(root == nullptr) return result;
        //先放入根节点
        st.push(root);
        //退一进二
        while(!st.empty()){
            TreeNode* curNode= st.top();
            st.pop();
            result.push_back(curNode->val);
            //先放左节点，再放右节点
            if(curNode->left) st.push(curNode->left);
            if(curNode->right) st.push(curNode->right);
        }
        //运用std空间里的reverse()来反转
        reverse(result.begin(),result.end());
        return result;
    }
}

2.广度优先遍历

按层数遍历，用一个辅助队列

class Solution{
public:
    vector<vector<int>> levelOrder(TreeNode* root){
        //存放每一层的遍历结果
        vector<vector<int>> result;
        //辅助队列
        queue<TreeNode*> que;
        
        if(root == nullptr) return result;
        
        //将头节点入队列
        que.push(root);
        
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            //对当前层进行遍历
            for(int i=0;i<size;i++){
                TreeNode* curNode =que.front();
                que.pop();
                vec.push_back(curNode -> val);
                if(curNode ->left) que.push(curNode ->left);
                if(curNode ->right) que.push(curNode ->right);
            }
            result.push_back(vec);
        }
       	return result;
    }
}