遍历方法

DFS

二叉树的 DFS 可以分为先序遍历、中序遍历、后序遍历。

非递归遍历

在二叉树中，我们可以使用非递归方法来实现 DFS，这种方法可以看作是模拟递归函数的调用栈。

以中序遍历为例，观察递归版本的中序遍历代码，大致框架如下：

vector<int> ans;

void dfs(Node *u)
{
    if (!u)
    {
        return;
    }
    dfs(u->left);
    ans.push_back(u);
    dfs(u->right);
}

可以发现，我们需要记录的是每个节点 u 具体在哪一行代码，u 可能是刚进入函数，也可能以及执行了 dfs(u->left)，是第二次遍历。为了模拟调用栈的代码执行位置，我们用一个 pair 来记录函数的状态，使用辅助 bool 变量来标明“当前指针在哪一行代码”。

实现如下：

stack<pair<TreeNode*, bool>> stk;
stk.push({root, false}); // call stack
while (!stk.empty())
{
	auto [u, state] = stk.top();
	stk.pop();
	if (!u)
	{
		continue;
	}
	else if (!state)
	{
		stk.push({u, true});
		stk.push({u->left, false});
	}
	else
	{
		ans.push_back(u->val);
		stk.push({u->right, false});
	}
}

实际上，机器执行的时候并不把所有

在中序遍历中，存在一个 dfs(u->right) 的尾递归，我们可以把它也优化为循环。 →（链接未公开）

我们可以首先尝试把尾递归优化为循环：

void dfs(Node *u)
{
    while (true)
    {
        if (!u)
        {
            return;
        }
        dfs(u->left);
        ans.push_back(u->val);
        u = u->right;
    }
}

然后再对上述代码进行调用栈模拟。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;
    TreeNode* u = root;

    while (u || !stk.empty()) {
        while (u) {
            stk.push(u);
            u = u->left;
        }

        u = stk.top();
        stk.pop();

        ans.push_back(u->val);

        u = u->right;
    }

    return ans;
}

BFS

二叉树的 BFS 又称为层次遍历。

算法

先序、中序、后序的转换

先序中序建树

LCR 124. 推理二叉树 - 力扣（LeetCode）

给出二叉树的先序 a 和中序 b，建立二叉树，并求出二叉树的后序 c。

思路：先序的第 1 个节点 a_1 一定是根节点，创建节点。在中序中找到 b_i = a_1，则中序 [1, i - 1] 的区间就是左子树，先序中对应位置 [2, i] 也是左子树。然后可以递归左右子树的前序、中序序列，转化为子问题。

实现：使用一个函数 build(pre_it, in_it, len) 记录以子段 a[p \cdots (p + l - 1)] 为先序、b[i \cdots (i + l - 1)] 为中序建立的二叉树，则可以递归。

TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
    int siz = preorder.size();
    TreeNode *rt = build(preorder.begin(), inorder.begin(), siz);
    return rt;
}

using It = vector<int>::iterator;
TreeNode* build(It pre_it, It in_it, int siz) {
    if (siz <= 0) {
        return nullptr;
    }
    int rt_val = *pre_it;
    TreeNode *rt = new TreeNode(rt_val);
    int l_siz = 0, r_siz;
    for (auto it = in_it; l_siz + 1 < siz; l_siz++, it++) {
        if (*it == rt_val) {
            break;
        }
    }
    r_siz = siz - 1 - l_siz;
    rt->left = build(pre_it + 1, in_it, l_siz);
    rt->right = build(pre_it + l_siz + 1, in_it + l_siz + 1, r_siz);
    return rt;
}