1回答

liuyubobobo

2021-02-18

已采纳

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

比如前序遍历是 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，包括后续的很多数据结构，关键是理解，熟悉递归这种最常用的程序设计方式，而不是仅仅在学习一种数据结构。

继续加油！：）

0

2

慕虎5119090

非常感谢！

2021-04-08

共2条回复