二叉树遍历 · Zwing's blog

层序遍历

层序遍历从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

层序遍历本质上属于广度优先遍历，也称广度优先搜索，它体现了一种 “一圈一圈向外扩展” 的逐层遍历方式。

层序遍历在实现上符合队列先进先出的特点，因此可以使用队列来实现层序遍历。

数组存储

struct TreeNode
{
    int val;
    int l;
    int r;
    TreeNode():val(0),l(0),r(0),p(0){}
};

void levelOrder(vector<TreeNode> &v,int root)
{
    queue<int> q;
    q.push(root);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        cout << v[cur].val << " ";
        if(v[cur].l)
        {
            q.push(v[cur].l);
        }
        if(v[cur].r)
        {
            q.push(v[cur].r);
        }
    }
}

指针

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *l;
    TreeNode *r;
    explicit TreeNode(int x):val(x),l(nullptr),r(nullptr){}
    // 析构略
};

void levelOrder(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode *cur = q.front();
        q.pop();
        cout << cur->val <<  " ";
        if(cur->l)
        {
            q.push(cur->l);
        }
        if(cur->r)
        {
            q.push(cur->r);
        }
    }
}

逐层操作

如果对每一层的操作有区别，那么要真正实现 “按层遍历”

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> v;
    if(!root) return v;
        
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        int curLevelSize = q.size(); //创新点
        vector<int> tmp;
        for(int i = 0; i < curLevelSize; i++){ // 这个循环内为一层
            root = q.front();
            q.pop();
            tmp.push_back(root->val);
            if(root->left){
                q.push(root->left);
            }
            if(root->right){
                q.push(root->right);
            }
        }
        v.push_back(tmp);
    }
    return v;
}

先序遍历

先序递归

void preOrder(TreeNode *root)
{
    if(root == nullptr)
    {
        return;
    }
    cout << root->val << " ";
    preOrder(root->l);
    preOrder(root->r);
}

先序迭代

void preOrder(TreeNode *root)
{
    stack<TreeNode*> s;
    TreeNode *cur = root;
    while(cur || !s.empty())
    {
        while(cur)
        {
            cout << cur->val << " "; // 根
            s.push(cur);
            cur = cur->l; // 往左走
        }
        cur = s.top(); // 循环结束，左走到底
        s.pop();
        cur = cur->r; // 往右走
    }
}

中序遍历

中序递归

void inOrder(TreeNode *root)
{
    if(root == nullptr)
    {
        return;
    }
    inOrder(root->l);
    cout << root->val << " ";
    inOrder(root->r);
}

中序迭代

void inOrder(TreeNode *root)
{
    stack<TreeNode*> s;
    TreeNode *cur = root;
    while(cur || !s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur = cur->l;
        }
        cur = s.top(); // 左走到底
        s.pop();
        cout << cur->val << " ";
        cur = cur->r;
    }
}

后序遍历

后序递归

void postOrder(TreeNode *root)
{
    if(root == nullptr)
    {
        return;
    }
    postOrder(root->l);
    postOrder(root->r);
    cout << root->val << " ";
}

后序双栈迭代

按根-右-左的顺序，再翻转

void postOrder(TreeNode *root)
{
    stack<TreeNode*> s1;
    stack<TreeNode*> s2;
    s1.push(root);
    while(!s1.empty())
    {
        TreeNode *cur = s1.top();
        s1.pop();
        s2.push(cur);
        if(cur->l)
        {
            s1.push(cur->l);
        }
        if(cur->r)
        {
            s1.push(cur->r);
        }
    }
    while(!s2.empty())
    {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

后序单栈迭代

void postOrder(TreeNode *root)
{
    stack<TreeNode*> s;
    TreeNode *cur = root;
    TreeNode *last = nullptr;  // 记录上次访问的节点
    
    while(cur || !s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur = cur->l;
        }
        
        cur = s.top();
        
        // 如果右子树不存在或右子树已经访问过
        if(cur->r == nullptr || cur->r == last)
        {
            cout << cur->val << " ";
            s.pop();
            last = cur;
            cur = nullptr;
        }
        else
        {
            cur = cur->r; // 转向右子树
        }
    }
}

一些拓展

中序、后序 => 先序

例题

由后序的末尾得根节点，再由中序的根节点位置，划分出左右子树，递归求解

注意构造先序时的顺序

#include <iostream>
using namespace std;
string pre;

void func(string& in,string& post)
{
    if (in.empty() || post.empty())
    {
        return;
    }
    char root = post.back(); // 后序变量最后者为根节点
    post.pop_back(); // 弹出根节点
    string subInL = in.substr(0, in.find(root)); // 0到根节点位置（不含）
    string subInR = in.substr(in.find(root) + 1); // 根节点位置到末尾
    string subPostL = post.substr(0, subInL.size());
    string subPostR = post.substr(subInL.size());
    pre.push_back(root); // 根
    func(subInL, subPostL); // 左
    func(subInR, subPostR); // 右
}

int main()
{
    string in;
    string post;
    cin >> in;
    cin >> post;
    func(in,post);
    cout << pre;
}

先序、中序 => 后序

例题

由先序的开头得根节点，再由中序的根节点位置，划分出左右子树，递归求解

注意构造后序时的顺序

#include <iostream>
using namespace std;
string post;

void func(string &pre,string &in)
{
    if (pre.empty() || in.empty())
    {
        return;
    }
    char root = pre.front();
    string subInL = in.substr(0,in.find(root));
    string subInR = in.substr(in.find(root)+1);
    string subPreL = pre.substr(1,subInL.length()); // 1始去掉根节点
    string subPreR = pre.substr(1+subInL.length());
    func(subPreL,subInL); // 左
    func(subPreR,subInR); // 右
    post.push_back(root); // 根
}

int main()
{
    string pre;
    string in;
    cin >> in;
    cin >> pre;
    func(pre,in);
    cout << post;
}

只要两个序中有中序，就一定能求出另一个序

先序、后序 => 中序

例题

实际上仅由先序和后序无法确定出唯一一棵树，因为无法确定左右子树

这里由先序和后序确定出可能的中序数量

假设：先序 abc，后序 cba

中序则有四种情况：cba、bca、acb、abc

    a      a      a       a
   /      /        \       \
  b      b          b       b
 /        \        /         \
c          c      c           c

只有无法确定是左子树还是右子树时中序数量才会增加（两种情况），且树形结构符合乘法原理，故结果为 \(2^{cnt}\)

那什么情况才不能确定左右子树？

    a
   / \
  b   c

先序 abc，后序 bca

    a      a
   /        \
  b          b

先序 ab，后序 ba

可见当先序和后序相邻两个字符位置相反时，此时子树根节点只有一个后代，无法确定左右子树

int main()
{
    string pre;
    string post;
    cin >> pre >> post;
    long long cnt = 0;
    for (int i = 0; i < pre.size()-1; i++)
    {
        for (int j = 1; j < post.size(); j++)
        {
            if (pre[i] == post[j] && pre[i+1] == post[j-1])
            {
                cnt++;
            }
        }
    }
    cout << (1 << cnt); // 2^cnt，注意必须带括号
}