如何利用二叉树的前序遍历算法建立一棵普通的二叉树

Question

波波老师，如何利用二叉树的前序遍历算法建立一棵普通的二叉树（不是二分搜索树），支持泛型的那种，因为之前学校老师教的是只能建立一棵每个结点是单个字符的二叉树。

Answer 1

liuyubobobo 2021-02-18 18:21:13

如果只有前序遍历的结果，是不能唯一确定一棵二叉树的。

比如前序遍历是 1, 2, 3，以下的数都满足条件：

    1
   /
  2
 /
3

    1
   /
  2
   \
    3

  1
 / \
2   3

    1
     \
      2
     /
    3

    1
     \
      2
       \
        3

三个节点的任意一个顺序就有 5 种可能，如果节点更多，可能性就更多了。

如果同时给定二叉树的前序遍历和中序遍历，或者前序遍历和后序遍历，可以唯一确定一棵二叉树。这是一个经典问题。

给定前序遍历和后序遍历结果，建立二叉树，Leetcode 上有这个问题，你可以参考：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

不过如果你看到这里，我建议你继续往后看，至少看完 BST 部分，再来研究这个问题。关键不是是不是二分搜索树的问题，而是你需要对在树上做递归有更加充分的理解，再看这个问题才更加得心应手。我们学习 BST，包括后续的很多数据结构，关键是理解，熟悉递归这种最常用的程序设计方式，而不是仅仅在学习一种数据结构。

继续加油！：）

• 提问者 慕虎5119090 #1

  哈哈，应该是我的问题表达有误，我的意思是想问怎么编写利用扩展的前序遍历序列构建二叉树

• 提问者 慕虎5119090 #2

  非常感谢！