二叉树的深度遍历

目录

深度优先遍历：

二叉树节点定义：?

递归法：

前序

中序?

后序

迭代法：

前序

中序

后序

迭代法（统一写法）

前序

中序

后序

广度优先遍历：

---

二叉树的遍历方法包括两种：深度优先遍历与广度优先遍历

下面分别介绍这两种遍历方法的具体实现。

代码随想录 (programmercarl.com)https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%A7%8D%E7%B1%BB

---

深度优先遍历：

? ? ? ? 即先往深走，遇到叶子节点再往回走。又包括前序、中序、后序遍历，可分别由递归法与迭代法实现。（PS:这里的三种顺序指的是中间节点的遍历顺序)

前序遍历：中左右

中序遍历：左中右

后序遍历：左右中

二叉树节点定义：
?

// Definition for a binary tree node.
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

递归法：

前序

 // 递归法
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == nullptr) return;
        vec.push_back(cur->val);
        traversal(cur->left, vec);
        traversal(cur->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preVec;
        if(root==nullptr) return preVec;
        traversal(root, preVec);
        return preVec;
    }
};

中序?

 // 递归法
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == nullptr) return;
        traversal(cur->left, vec);
        vec.push_back(cur->val);
        traversal(cur->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> mid_vec;
        if(root == nullptr) return mid_vec;
        traversal(root, mid_vec);
        return mid_vec;
    }
};

后序

 // 递归法
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == nullptr) return;
        traversal(cur->left, vec);
        traversal(cur->right, vec);
        vec.push_back(cur->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> post_vec;
        if(root == nullptr) return post_vec;
        traversal(root, post_vec);
        return post_vec;
    }
};

迭代法：

前序

 // 迭代法
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preVec;
        stack<TreeNode*> preStack;
        if(root==nullptr) return preVec;

        preStack.push(root);
        while(!preStack.empty()){
            TreeNode* cur = preStack.top();
            preStack.pop();
            preVec.push_back(cur->val);     // 前序
            // 中节点的右左入栈，左右出栈
            if(cur->right) preStack.push(cur->right);
            if(cur->left) preStack.push(cur->left);
        }
        return preVec;
    }
};

中序

 // 迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> mid_vec;
        stack<TreeNode*> mid_stack;
        if(root == nullptr) return mid_vec;
        
        TreeNode* cur = root;
        while(cur || !mid_stack.empty()){
            if(cur){
                mid_stack.push(cur);
                cur = cur->left;
            }
            else{
                cur = mid_stack.top();
                mid_stack.pop();
                mid_vec.push_back(cur->val);    // 中序
                cur = cur->right;
            }
        }

        return mid_vec;
    }
};

后序

 // 迭代法
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> post_vec;
        stack<TreeNode*> post_stack;
        if(root == nullptr) return post_vec;
        post_stack.push(root);

        while(!post_stack.empty()){
            TreeNode* cur = post_stack.top();
            post_stack.pop();
            post_vec.push_back(cur->val);    //前序（后面逆转)
            //左右入栈，右左出栈
            if(cur->left) post_stack.push(cur->left);
            if(cur->right) post_stack.push(cur->right);
        }
        // 中右左->左右中
        reverse(post_vec.begin(),post_vec.end());
        return post_vec;
    }
};

迭代法（统一写法）

前序

 // 迭代法(统一风格)
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preVec;
        stack<TreeNode*> preStack;
        if(root) preStack.push(root);

        while(!preStack.empty()){
            TreeNode* cur = preStack.top();
            if(cur){    // 入栈标记处理节点
                preStack.pop();
                if(cur->right) preStack.push(cur->right);   //右入栈
                if(cur->left) preStack.push(cur->left);     //左入栈
                preStack.push(cur);                        //中入栈
                preStack.push(nullptr);                    //push空节点，标记处理节点
            }
            else{   // 遇空节点出栈处理
                preStack.pop();
                preVec.push_back(preStack.top()->val);
                preStack.pop();
            }
        }
        return preVec;
    }
};

中序

 // 迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> mid_vec;
        stack<TreeNode*> mid_stack;
        if(root) mid_stack.push(root);
        
        while(!mid_stack.empty()){
            TreeNode* cur = mid_stack.top();
            if(cur){    // 入栈标记处理节点
                mid_stack.pop();
                if(cur->right) mid_stack.push(cur->right);
                mid_stack.push(cur);
                mid_stack.push(nullptr);
                if(cur->left) mid_stack.push(cur->left);
            }
            else{       // 遇空节点出栈处理
                mid_stack.pop();
                mid_vec.push_back(mid_stack.top()->val);    // 中序
                mid_stack.pop();
            }
        }
        return mid_vec;
    }
};

后序

 // 迭代法(统一风格)
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> post_vec;
        stack<TreeNode*> post_stack;
        if(root) post_stack.push(root);

        while(!post_stack.empty()){
            TreeNode* cur = post_stack.top();
            if(cur){    // 入栈标记处理节点
                post_stack.push(nullptr);                       // 中
                if(cur->right) post_stack.push(cur->right);     // 右
                if(cur->left) post_stack.push(cur->left);       // 左
            }
            else{       // 遇空节点出栈处理
                post_stack.pop();
                post_vec.push_back(post_stack.top()->val);
                post_stack.pop();
            }

        }
        return post_vec;
    }
};

广度优先遍历：

????????一层一层的去遍历。
? ? ? ??