二叉树（2）

前序遍历

前序是根-左-右。

递归写法：

void preorder(TreeNode* root){
	if(!root) return;  //记得一定要先判断是不是nullptr呀！
	cout << root->val << " ";
	preorder(root->left);
	preorder(root->right);
}

用栈写法（FILO，不能用队列）：

vector<int> preorderIter(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        res.push_back(cur->val);          // 根先处理
        if (cur->right) st.push(cur->right); // 右先压（后出）
        if (cur->left) st.push(cur->left);   // 左后压（先出）
    }
    return res;
}

中序遍历

左-根-右。常用来检验 BST （二叉搜索树），中序遍历BST = 严格升序。

递归写法：

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";   // 根中间
    inorder(root->right);
}

栈（一直左到底->弹出来处理当前节点->拐右边）

vector<int> inorderIter(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;      // 一直往左
        }
        cur = st.top(); st.pop();
        res.push_back(cur->val);  // 左到底了，处理根
        cur = cur->right;         // 再走右
    }
    return res;
}

后序遍历

左-右-根。先看看左右子树情况如何，再决定我要做什么。

递归写法：

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";   // 根最后
}

栈写法：

vector<int> postorderIter(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        res.push_back(cur->val);
        if (cur->left) st.push(cur->left);   // 左先压
        if (cur->right) st.push(cur->right); // 右后压（先出）
    }
    reverse(res.begin(), res.end());
    return res;
}