LeetCode 经典问题分类总结:二叉树遍历

2020/02/15 LeetCode

之前刷过一些题并做过总结,想着干脆慢慢把笔记都挪到这里。本文总结二叉树遍历的各种问题,并结合 LeetCode 原题给出 C++ 的解法。本文题目前的题号就是 LeetCode 原题的题号(不过似乎某些题目现在的题号变了)。


普通的二叉树前序、中序、后序遍历

11. Binary Tree Preorder Traversal (Medium) 前序遍历

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

递归法

前序遍历的标准流程:中->左->右。

vector<int> preorderTraversal(TreeNode* root) {
     vector<int> result;
     preorder(root, result);
     return result;
 }
// Recursion helper function
void preorder(TreeNode* root, vector<int>& result)
{
     if (root == 0)
         return;
     result.push_back(root->val);
     preorder(root->left, result);
     preorder(root->right, result);
}

直观迭代法:把所有节点放入 stack

这里仅使用一个堆栈来记录当前访问节点的位置,该方法会把所有节点推入堆栈。这也是最直观的一种方法。优点是,很容易扩展到多叉树遍历。

vector<int> preorderTraversal(TreeNode* root) 
{
     if (root == 0)
         return vector<int>();
     vector<int> result;
     stack<TreeNode*> st;
     st.push(root);
     while (!st.empty())
     {
         TreeNode* node = st.top();
         st.pop();
         result.push_back(node->val);
         // Push right first and left second, since we want to visit from left -> right
         if (node->right)
             st.push(node->right);
         if (node->left)
             st.push(node->left);
    }
     return result;
}

经典迭代法:只把部分节点放入 stack

这里使用一个节点 node 记录当前访问的位置,这样做的优点是:

  • 更好的控制遍历方向;
  • 无需将所有节点推入堆栈。

该方法每次向当前节点 node 的 left child 方向遍历,并且只把每个节点的 right child 放入堆栈。这种做法也是 Wiki 的 Tree Traversal 中所示的标准方法。后面的中序和后序遍历的迭代法和这种方法类似。

vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> res;
    if (root == nullptr)
        return res;
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (node || !st.empty())
    {
        if (node)
        {
            res.push_back(node->val);
            // Only saves right child to the stack,
            // since node itself goes to the left child each time
            if (node->right != nullptr)
                st.push(node->right);
            node = node->left;
        }
        else
        {
            // If no left child, get the latest node from stack which
            // is from the right sub-tree.
            node = st.top();
            st.pop();
        }
    }
    return res;
}

Follow Up:589. N-ary Tree Preorder Traversal 多叉树前序遍历

递归很简单,既不给了。迭代法可以仿照前序遍历的直观迭代版即可。因为此时是多叉树,故要把所有节点放入stack中。

vector<int> preorder(Node* root)
{
    vector<int> res;
    if (root == nullptr)
        return res;
    stack<Node*> st;
    st.push(root);
    while (!st.empty())
    {
        Node* node = st.top();
        st.pop();
        res.push_back(node->val);
        for (int i = int(node->children.size()) - 1; i >= 0; i--)
        {
            if (node->children[i])
                st.push(node->children[i]);
        }
    }
    return res;
}

94. Binary Tree Inorder Traversal (Medium) 中序遍历

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].

递归法

中序遍历标准流程是左->中->右,即对于某个输入节点,先递归该节点的左子树,然后visit该节点,最后递归该节点的右子树。

void inorder(TreeNode* root, vector<int>& result)
{
     if (root == 0)
         return;
     inorder(root->left, result);
     result.push_back(root->val);
     inorder(root->right, result);
}
 
vector<int> inorderTraversal_recursive(TreeNode* root) 
{
    vector<int> result;
    inorder(root, result);
    return result;
}

迭代法

类似前序遍历的经典迭代法,使用堆栈来记录所有已经遍历过的节点,并额外使用一个节点来控制二叉树遍历的方向。不过,此时该方法把全部节点都放入了stack中。

vector<int> inorderTraversal_iterative(TreeNode* root)
{
    if (root == 0)
        return vector<int>();
    vector<int> result;
    stack<TreeNode*> s;
    TreeNode* node = root; // use a node to traverse the tree
    while (node != 0 || !s.empty())
    {
        if (node)
        {
            s.push(node);
            node = node->left; // traverse to the left node
        }
        else
        {
            // Now is the time to pop the top node from the stack
            node = s.top();
            s.pop();
            result.push_back(node->val); // visit the node
            node = node->right;// traverse to the right node
        }
    }
    return result;
}

Follow Up: 在检索二叉树(BST)中的应用

中序遍历在 BST 二叉检索树中的应用有很多,这是因为,一个 BST 的中序遍历一定是排好序并严格递增的。常见的几个应用有:

  • 验证 BST(LC98: Validate Binary Search Tree):一种方法是,使用基于 stack 的中序遍历,并使用一个节点 pre 记录上一个访问过的节点。每次 pop 出来的新节点 node 的值必须要大于 pre 的值,然后更新 pre 为当前的 node, 继续循环即可。
  • 找出 BST 中第 k 小的值(LC230: Kth Smallest Element in a BST)。当然,一种直观法是运行一整遍中序遍历,记录所有结果,那么第 k 个值就是所求。不过它所需空间是 O(n)。另一种方法是,还是使用基于 stack 的中序遍历,每次 pop 出新节点便 k–,当 k == 0 时的节点便是第 k 小的节点了。

145. Binary Tree Postorder Traversal (Hard) 后序遍历

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:

Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

递归法

标准顺序:左 -> 右 -> 中。没啥好说的。

void postorder(TreeNode* root, vector<int>& result)
{
    if (root == 0)
        return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->val);
}

vector<int> postorderTraversal_recursive(TreeNode* root)
{
    vector<int> result;
    postorder(root, result);
    return result;
}

迭代实现:经典法

为了实现左 -> 右 -> 中的遍历顺序,使用 stack 并注意访问每个节点和左右子节点的次序。首先还是不断向左遍历,到头后便使用堆栈退回上一个节点并换到右边,然后继续向左。到达叶子节点后自然可以访问该节点了。重复此过程即可。

后序遍历有一点特别的地方:访问一个节点 node 时,我们需要判断该节点的左右节点是否都被访问过了。判断左节点很容易,因为我们都是一直向左走到头的,因此只要是从 stack 中 pop 出来的节点,它的左节点一定是已经访问过的。不过,判断右节点有些特别,如何知道右节点是否已经被访问?一个简单的方法是,额外使用一个变量 last 记录上次刚刚访问的节点,于是,只要判断 last 和 node->right 的关系就行了。如果相等,说明右节点也被访问了,此时便访问 node,并更新 last = node;不是的话,则移动 node = node->right,继续遍历就行。当然也可以额外定义一个 vector 或 map 记录每个节点是否被访问,不过显然空间要大很多。

该方法也是将全部节点都放入了 stack 中一遍。

vector<int> postorderTraversal_iterative(TreeNode* root)
{
    if (root == 0)
        return vector<int>();
    stack<TreeNode*> st;
    TreeNode* lastvisitednode = 0;
    TreeNode* node = root;
    vector<int> result;
    while (node || !st.empty())
    {
        if (node)
        {
            st.push(node);
            node = node->left;
        }
        else
        {
            node = st.top();
            if (node->right && node->right != lastvisitednode)
                node = node->right;
            else
            {
                st.pop();
                result.push_back(node->val);
                lastvisitednode = node;
                node = 0;
            }
        }
    }
    return result;
}

迭代实现 2:翻转前续遍历的结果

很巧妙的思想:后序遍历是 left -> right -> root,而前续遍历则是 root -> left -> right。所以,首先将前续遍历修改为 root -> right -> left 的形式,最后 reverse 所得的结果,即可得到后序遍历的结果了。

vector<int> postorderTraversal_reverse(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    vector<int> result;
    if (root == NULL)
        return result;
    nodeStack.push(root);
    while (!nodeStack.empty())
    {
        TreeNode* node = nodeStack.top();
        result.push_back(node->val);
        nodeStack.pop();
        if (node->left)
            nodeStack.push(node->left);
        if (node->right)
            nodeStack.push(node->right);
    }
    reverse(result.begin(), result.end());
    return result;
}

Follow Up:590. N-ary Tree Postorder Traversal 多叉树后序遍历

将二叉树扩展成了 N 叉树,要求后序遍历,其顺序是,先访问从左到右的 children,然后访问根节点。

递归法

类似二叉树的后序遍历,只是这里要先遍历全部的孩子节点,最后再访问根节点本身。

vector<int> postorder(Node* root)
{
    vector<int> res;
    helper(root, res);
    return res;
}
void helper(Node* root, vector<int>& res)
{
    if (root == nullptr)
        return;
    for (Node* node : root->children)
        helper(node, res);
    res.push_back(root->val);
}

迭代法

参考后序遍历的迭代法,实现 middle -> right -> left 遍历,然后 reverse 结果。

vector<int> postorder(Node* root)
{
    vector<int> res;
    if (root == nullptr)
        return res;
    stack<Node*> st;
    st.push(root);
    while (!st.empty())
    {
        Node* node = st.top();
        st.pop();
        for (Node* curr : node->children)
            st.push(curr);
        res.push_back(node->val);
    }
    reverse(res.begin(), res.end());
    return res;
}

O(1) 空间的二叉树遍历:Morris Traversal算法

参考:Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间)

普通的二叉树的前中后序方法都需要 O(n) 的额外空间。而一种称为 Morris Traversal 的算法可以实现仅需 O(1) 空间的遍历。它的核心思想是,为了能够在遍历过程中能够不用额外的 stack 空间就能回到已经访问过的节点,该算法在遍历过程中修改了二叉树的部分叶子结点的 right 节点(它本身为 null)指向该叶子结点在中序遍历中的下一个节点。另外,在遍历过程中又会不断将修改后的这个 right 节点恢复原状。上面链接中有图。有意思的是,无论是 Morris Traversal 前中后序遍历,其访问节点的顺序流程完全相同,不同之处在于打印节点的位置。

该算法的优点自然是仅需 O(1) 的额外空间了。缺点是:整个过程中,每个节点最多被访问了两次,因此它的时间最坏应当是 O(2n)。另外,它需要对二叉树修改,因此不适用于 read-only 的二叉树。

中序遍历

前序遍历和中序遍历的过程非常类似,只是在打印节点的时候有一点点区别而已。这里先介绍中序遍历,因为所有的前中后序遍历修改的叶子节点的 right 指针都指向它在中序遍历中的下一个节点。

中序遍历的流程其实不难,它基于普通的二叉树中序遍历的迭代法的标准流程。特别之处是,对于每一个节点 curr,Morris Traversal 算法为之定义了一个 pre 节点:pre 就是 curr 的左子树中最右下边那个节点,即中序遍历中的上一个节点。它的作用就是为了在遍历中不用 stack 也能够回到已经访问过的节点,以达到 O(1) 空间的效果。

当第一次访问某个节点 curr 时,如果 curr 的 pre 节点是叶子节点,就修改 pre->right = curr。这样做的原因是,当之后遍历到 pre 这个节点时,就可以通过 pre->right 回到 curr,即 pre 的下一个节点了。而当再次回到 curr 时(即第二次访问 curr),再次找到它在中序遍历中的上一个节点 pre,如果 pre->right == curr,那么将其恢复原状,即 pre->right = nullptr。

找到 curr 的 pre 节点其实挺简单的,一个循环就足够了。如果树是 BST 的话,pre 其实就是 curr 的紧挨着的上一个比它小的节点。

算法流程

初始时 curr = root。设置 while(curr) 循环,对于 curr:

  • 如果 curr->left 存在,那么首先找到 curr 的 pre 节点。然后:
    • 如果 pre->right == nullptr,说明此时是第一次访问到 curr,那么设置 pre->right = curr,然后向左走 curr = curr->left。这是因为,此时是第一次访问 curr,根据中序遍历的左中右流程,肯定要先向左走。注意此时不能打印 curr,因为它的左子树尚未访问完毕。
    • 如果 pre->right 存在,那么它肯定等于 curr,即此时是第二次访问 curr。此时打印 curr->val,然后向右走 curr = curr->right。这是因为,此时是第二次访问 curr,表明它和它的左子树已经全部访问完毕了,因此要向右走。
  • 如果 curr->left 不存在,说明左子树不存在,直接打印当前节点 curr->val,再向右走 curr = curr->right。

注意,该流程其实是所有的前中后序遍历的标准流程,它们之间区别非常小,并且都只是在打印 curr 的位置不同而已。

这里有一点挺特别的:pre->right 要么不存在,要么就等于 curr,没有其他可能了。这其实挺容易理解,因为 pre 的定义就是左子树的最右下角的节点。

下面的图演示了整个中序遍历的流程,加深的节点是打印的节点。

代码就是上面流程的实现,难度不大。

void morrisInorder(TreeNode* root, vector<int>& res)
{
    if (!root)
        return;
    auto curr = root;
    while (curr)
    {
        if (curr->left == nullptr)
        {
            res.push_back(curr->val);
            curr = curr->right;
        }
        else
        {
            auto pre = curr->left;
            while (pre->right && pre->right != curr)
                pre = pre->right;

            if (pre->right == nullptr)
            {
                pre->right = curr;
                curr = curr->left;
            }
            else
            {
                res.push_back(curr->val);
                pre->right = nullptr;
                curr = curr->right;
            }
        }
    }
}

前序遍历

前序遍历和中序遍历流程完全一致,唯一区别就是打印 curr 的位置。因为前序是“中左右”的顺序,因此第一次遇到 curr 时就要打印,而第二次遇到时则不需要打印了。

void morrisPreorder(TreeNode* root, vector<int>& res)
{
    if (!root)
        return;
    auto curr = root;
    while (curr)
    {
        if (curr->left == nullptr)
        {
            res.push_back(curr->val);
            curr = curr->right;
        }
        else
        {
            auto pre = curr->left;
            while (pre->right && pre->right != curr)
                pre = pre->right;

            if (pre->right == nullptr)
            {
                res.push_back(curr->val); // only difference from inorder
                pre->right = curr;
                curr = curr->left;
            }
            else
            {
                pre->right = nullptr;
                curr = curr->right;
            }
        }
    }
}

后序遍历

后序遍历稍微就多一些tricky的地方了。上面的前中序流程中,当访问完 pre 后再次回到 curr 时,此时只说明已经访问了 curr 的左子树的全部节点而已。而后序遍历的顺序是“左右中”,即还需访问完 curr 的全部右子树后,才能打印 curr。因此,这似乎像是要第三次访问 curr 的感觉?这几乎不可能只用一次遍历就实现啊。而实际上,这前中后遍历的节点的访问/遍历顺序都是完全相同的,只是打印节点的位置不同而已。后序遍历中使用了一点点特别的技巧。因此,我们可以分析一下访问节点的流程,然后推导出后序遍历中打印/访问节点究竟应该在什么时候。

首先,第一次访问 curr 节点时就打印它,这肯定是前序遍历。第二次访问 curr 节点时打印它,这就是中序遍历,因为这意味着curr的左子树已经访问完毕了。如果每个节点最多只被访问两次的话,那么什么时候后序遍历打印 curr?此时打印节点的时机非常巧妙:当第二次回到某个节点curr时,我们就打印一组包括 curr->left 的节点(注意,此时并不是打印 curr 本身):此时我们要倒着打印从 curr->left(即 curr 左子树根节点)开始,一直沿着右边的路径直到叶子节点(即 curr 的 pre 节点)为终点为止的这一组节点。

有关这个打印的说明:

  • 首先,根据前面的标准遍历流程,首先打印左叶子节点(即该叶子节点是左节点)。当第二次回到它的父亲节点 curr 时,此时打印这个左叶子节。而容易看出,此时 curr->left 就等于 pre,即此时其实只打印左叶子节点这一个节点。
  • 接着,对于其它节点来说,第二次回到 curr 时,准备打印从 curr->left 到 pre 的一组节点。从 pre 开始向上走直到 curr->left 节点为止,这批节点正好就是各个对应子树的根节点,它们同时也是它们的父节点的右节点。因此,倒着从底向上打印的话,就能够满足,先打印右节点,再打印根节点这个后序遍历的顺序了。由于它们的左节点已经打印过了,因此这种打印方法就能够满足后序遍历的要求。
  • 如果按照这种方法,显然是无法打印整个树的根节点 root 的,因为它根本没有 parent。因此,在整个循环开始前,我们要建立一个 dummy 节点作为父节点,并设置 dummy->left = root,然后从 curr = dummy 开始遍历。这样的话,遍历过程中就能够保证,树的某个节点会最终指向 dummy,从而可以回到 dummy,然后调用打印函数打印 root 等一组节点了。

这是一个后序遍历的流程图,浅蓝色是打印节点的顺序,深蓝色那一个节点是 dummy。

实现上,遍历的流程和前中序是完全一样的,只是打印节点的方法不同。不过,此时需要额外定义一个函数 printNodes(start, end),打印 curr->left 和 pre 之间的节点。而在树中,节点连接顺序显然是从 curr->left 到 pre 的,因此我们需要倒着打印。实现上,为了严格遵循节点的访问顺序,并且保持 O(1) 的空间复杂度,我们需要首先 reverse 从 curr->left 到 pre 这个“链表”的节点顺序,然后打印从 pre 到 curr->left,最后再次 reverse 从 pre 到 curr->left 以恢复原始二叉树。这种 reverse 过程显然会增加时间,不过也就是增加了 O(n) 而已。而 in-place reverse linked-list 的额外空间依然是 O(1),并未增加空间复杂度。

void reverseNodes(TreeNode* from, TreeNode* to)
{
    if (from == to)
        return;
    auto prev = from, curr = from->right;
    while (prev != to)
    {
        auto tmp = curr->right;
        curr->right = prev;
        prev = curr;
        curr = tmp;
    }
}
void printNodes(TreeNode* from, TreeNode* to, vector<int>& res)
{
    reverseNodes(from, to);
    auto curr = to;
    while (true)
    {
        res.push_back(curr->val);
        if (curr == from)
            break;
        curr = curr->right;
    }
    reverseNodes(to, from);
}
// Postorder
void morrisPostorder(TreeNode* root, vector<int>& res)
{
    if (!root)
        return;
    auto dummy = new TreeNode(0);
    dummy->left = root;
    auto curr = dummy;
    while (curr)
    {
        if (curr->left == nullptr)
        {
            curr = curr->right;
        }
        else
        {
            auto pre = curr->left;
            while (pre->right && pre->right != curr)
                pre = pre->right;
            if (pre->right == nullptr)
            {
                pre->right = curr;
                curr = curr->left;
            }
            else
            {
                printNodes(curr->left, pre, res); // only place to print
                pre->right = nullptr;
                curr = curr->right;
            }
        }
    }
}

其余的二叉树遍历形式

102. Binary Tree Level Order Traversal (Easy) 按行遍历

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

递归实现

本题目的难点在于如何将同一层的节点放在一起输出。直观想法是,访问每个节点时,判断该节点的深度,然后放在结果数组的相应位置。不过,在使用 vector 存储每一层的数据时,由于开始时并不知道输入的二叉树一共有多少层,因此需要在程序运行之中不断更新该 vector 的大小。

void traverseTree(vector<vector<int> >& result, TreeNode* root, int depth)
{
    if (root == 0)
        return;

    // Note: the following step is very necessary, since the
    // "result" is very possibly to be empty when comming to the
    // current depth at the first time. So it needs to be updated.
    if (result.size() == depth)
        result.push_back(vector<int>());

    result[depth].push_back(root->val);
    traverseTree(result, root->left, depth + 1);
    traverseTree(result, root->right, depth + 1);
}
vector<vector<int> > levelOrder_Recursive(TreeNode *root)
{
    vector<vector<int> > result;
    traverseTree(result, root, 0);
    return result;
}

BFS 经典法

使用 queue 可以很容易实现二叉树的层次遍历,只要不断的从队列中 pop 出节点,然后 push 其全部 children 节点即可。但同样的,难点在于如何判断一层的节点有多少个。实际上,我们每次都将一层节点全部 pop 出来,与此同时将下一层的所有节点 push 到队列中,因此,每次我们 pop 出来的正好是同一层的全部节点。因此,不妨在开始时记录 queue 的元素个数 n,那么 pop 了 n 次之后便是经过了一层。一个 for 循环便可实现。

vector<vector<int> > levelOrder_iterative(TreeNode *root)
{
    vector<vector<int> >  result;
    if (!root)
        return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        int n = q.size();
        vector<int> row(n);
        // Now the queue only stores the whole level
        for (int i = 0; i != n; ++i)
        {
            TreeNode* t = q.front();
            q.pop();
            row[i] = t->val;
            if (t->left)
                q.push(t->left);
            if (t->right)
                q.push(t->right);
        }
        result.push_back(row);
    }
    return result;
}

BFS 中使用 marker node

另一种非常巧妙的方法是:在 queue 中加入一个空节点 nullptr 作为 marker node,用来标记到达了某一层的末尾。注意到,当到达了某一层的末尾时,队列中存储的便只剩下一层的所有节点。因此,此时可以继续增加一个空节点到队列中,重复这个过程直到结束。这种使用 marker node 的方法非常经典,经常用来扩展到其他问题中。

vector<vector<int> > levelOrder(TreeNode *root) 
{
    vector<vector<int> >  result;
    if (!root) 
        return result;
    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr); // marker node 
    vector<int> cur_vec; // stores the values for each level
    while (!q.empty()) 
    {
        TreeNode* t = q.front();
        q.pop();
        if (t == nullptr)
        {
            // Now this level is ended. 
            result.push_back(cur_vec);
            cur_vec.resize(0);
            if (q.size() > 0) // add a new marker node
                q.push(nullptr);
        }
        else 
        {
            cur_vec.push_back(t->val);
            if (t->left) 
                q.push(t->left);
            if (t->right)
                q.push(t->right);
        }
    }
    return result;
}

107. Binary Tree Level Order Traversal II (Medium) 倒着按行遍历

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

本题目要求从底部到顶部进行按行遍历,其实就是把按行遍历的结果反过来输出。因此,可以直接照搬前面 LC102. Binary Tree Level Order Traversal 问题 的按行遍历法,最后把结果翻转一下就行了。这个代码就不给了。

下面给出的是一种直接的递归法。

递归法

直接递归法稍微麻烦一点。首先需要遍历一遍得到最大的深度。然后还是使用按行遍历方法,把每一层节点放在结果数组中对应的倒着数的位置。

vector<vector<int>> levelOrderBottom(TreeNode* root)
{
    vector<vector<int>> res(getDepth(root));
    helper(root, 0, res);
    return res;
}

int getDepth(TreeNode* root)
{
    return (root == nullptr) ? 0 : max(getDepth(root->left), getDepth(root->right)) + 1;
}

void helper(TreeNode* root, int depth, vector<vector<int>>& res)
{
    if (root == nullptr)
        return;
    res[res.size() - depth - 1].push_back(root->val);
    helper(root->left, depth + 1, res);
    helper(root->right, depth + 1, res);
}

Search

    Table of Contents