二叉树的遍历

---

二叉树的遍历

二叉树的定义

//二叉树
class TreeNode{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}

};

广度优先搜素

借助使用队列（queue）来存储遍历的节点,按照二叉树的每一层从前到后的顺序进行遍历

vector<vector<int>> traversal(TreeNode* root){
    vector<vector<int>> res;
    if (root== nullptr){
        return res;
    }
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()){
        int size=que.size();
        vector<int> temp;
        for (int i = 0; i < size; ++i) {
            TreeNode* tempNode=que.front();
            que.pop();
            temp.push_back(tempNode->val);
            if (tempNode->left){
                que.push(tempNode->left);
            }
            if (tempNode->right){
                que.push(tempNode->right);
            }
        }
    }

    return res;

}

深度优先搜索

递归法：

vector<int> res;

//前序遍历：中左右
void preTraversal(TreeNode* cur){
    if (cur== nullptr){
        return;
    }
    res.push_back(cur->val);
    traversal(cur->left);
    traversal(cur->right);
}
//中序遍历：左中右
void midTraversal(TreeNode* cur){
    if (cur== nullptr){
        return;
    }
    traversal(cur->left);
    res.push_back(cur->val);
    traversal(cur->right);
}
//后序遍历：左右中
void postTraversal(TreeNode* cur){
    if (cur== nullptr){
        return;
    }
    traversal(cur->left);
    traversal(cur->right);
    res.push_back(cur->val);
}

迭代法：

vector<int> res;

//前序遍历：中左右
void traversal(TreeNode* cur){
    if (cur== nullptr){
        return;
    }
    stack<TreeNode*> st;
    st.push(cur);
    while (!st.empty()){
        TreeNode* temp=st.top();
        st.pop();
        res.push_back(temp->val);
        if (temp->right){
            st.push(temp->right);
        }
        if (temp->left){
            st.push(temp->left);
        }
    }
}

//后序遍历：左右中
void postTraversal(TreeNode* cur){
    if (cur== nullptr){
        return;
    }
    stack<TreeNode*> st;
    st.push(cur);
    while (!st.empty()){
        TreeNode* temp=st.top();
        st.pop();
        res.push_back(temp->val);
        if (temp->left){
            st.push(temp->left);
        }
        if (temp->right){
            st.push(temp->right);
        }
    }
    //注意：上面的顺序时中游右左，经过下面的调整变成了左右中
    reverse(res.begin(),res.end());
}

//中序遍历:左中右
void midTraversal(TreeNode* root){
    if (root==nullptr){
        return;
    }
    stack<TreeNode*> st;
    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;
        }
    }
}