二叉树遍历专题

10 Dec 2023

阅读时长 ~1 分钟

传统DFS方式

:::info 主要是模拟递归时候，先序由于立即访问val是默认最简单的，中序和后序模拟时候有两种常见方案，后序还有一种额外的方案：借助先序逆转结果（当然这一种不是严格意义的后序次序访问） :::
1. 先序 ```cpp vector res; void predfs(TreeNode* node){ res.push_back(node->val); predfs(node->left); predfs(node->right); }

vector preorderTraversal(TreeNode* node) { stack<TreeNode*> s; s.push(node); while(!s.empty()){ node = s.top(); s.pop(); if(!node) continue; res.push_back(node->val); s.push(node->right); s.push(node->left); } return res; }

:::warning
判断nullptr 注意点: 
while(!s.empty() && !s.top()) 👈容易写错成这样，nullptr需要跳过而不是直接终止
还有种写法，不让nullptr左右子树加入栈中，然后需要单独判定传入root是否为空。
:::

   2. 中序
:::tips
中序递推版本和先序迥异，由于不能立即visit，我们需要优先左子树，再visit，然后右子树；

      1. 两种只是写法不同，本质都是不断深入左子树，当左子树没了，那就visit，然后切换到右子树分支再来
:::
```cpp
vector<int> res;
void indfs(TreeNode* node){
	predfs(node->left);
    res.push_back(node->val);
    predfs(node->right);
}

// 写法1 直观模拟
// 由于一个while是一个完整的单左分支DFS逻辑, 因此不需预先把root入栈 
vector<int> inorderTraversal(TreeNode* node) {
    stack<TreeNode*> s;
    while(1){
        while(node){
            s.push(node);
            node = node->left;
        }
        if(s.empty()) break;
        node = s.top();
        s.pop();
        res.push_back(node->val);
        node = node->right;
    }
    return res;
}
//写法1的变形简洁版：模仿法1走到NULL，其实就是法1内循环去掉了看上去更清爽
vector<int> inorderTraversal(TreeNode* node) {
 stack<TreeNode*> st;
 while (node || !st.empty()) {
     if (node) { // 指针来访问节点，访问到最底层
         st.push(node); // 将访问的节点放进栈
         node = node->left; // 左
     }else{
         node = st.top(); // 从栈⾥弹出数据
         st.pop();
         res.push_back(node->val); // 中
         node = node->right;
     }
 }  
}

//写法2（小饶） 和1不同的是，1是先走到NULL，这个法2是走到左叶子就停。
vector<int> inorderTraversal(TreeNode* node) {
    stack<TreeNode*> s;
	while(node || !s.empty()){
        if(!node) {
            //出栈找历史parent节点
            node = s.top(); 
            s.pop();
            //左路走过了，直接右路
            res.push_back(node->val);
        	node=node->right;
        }else if(!node->left){
            //左子树null，切右子树
            res.push_back(node->val);
        	node=node->right;
        }else{
            //一路左路缓存
            s.push(node);
            node = node->left;
        }
	}
	return res;
}

//法2再换个简洁风格，也是走到最左叶子就停下来read
vector<int> inorderTraversal(TreeNode* node) {
    stack<TreeNode*> s;
    vector<int> res;
    while(node || !s.empty()){
        if(!node){
            node = s.top();
            s.pop();
        }else
            while(node->left){
                s.push(node);
                node=node->left;
            }
        res.push_back(node->val);
        node=node->right;
    }
    return res;
}

后序 ```cpp vector res; void postdfs(TreeNode* node){ predfs(node->left); predfs(node->right); res.push_back(node->val); } // 1.特殊法（左右根逆反访问即根右左，正好借助先序遍历模板）（得到逆访问序列最后再reverse） vector postTraversal(TreeNode* node) { stack<TreeNode*> s; s.push(node); while(!s.empty()){ node = s.top(); s.pop(); if(!node) continue; res.push_back(node->val); s.push(node->left); //此处交换一下 s.push(node->right); } reverse(res.begin(), res.end()); //逆转 return res; }

// 2.

---

- **大一统写法（递推）**
:::success
核心就是：用额外空间标记是否首次处理，这里对任何节点都首次处理里只去入栈访问次序，只有第二次碰到时候才是真正visit时刻，其实就是完完全全对递归的记忆化模拟。 
:::
```cpp
void traverse(...){
	stack<pair<TreeNode*,bool>> s;
    s.push({root,0});
    while(!s.empty()){
        auto tmp=s.top();
        s.pop();
        if(tmp.second){
        }else{
            tmp.second = 1;
            s.push({tmp.first->right,0});
            s.push(tmp);
            s.push({tmp.first->left, 0});
        }
}

🥁-Algorithm