algorithm - 寻找二叉树的边界

Question

我们有一个二叉搜索树；我们需要找出它的边界。

所以，如果二叉树是

           10
       /         \
     50           150
    /  \         /   \
  25    75     200    20
 / \           /      / \
15 35        120    155 250 

它应该打印出 50 25 15 35 120 155 250 20 150 10。

如果二叉树是

               10
           /         \
         50           150
        /  \         /   
      25    75     200   
     / \   / \    
    15 35 65 30  

它应该像 50 25 15 35 65 30 200 150 10。

如何做到这一点？将此概括为二叉树会使问题变得更难吗？

我们也将不胜感激通过链接提供的任何帮助。

P.S.:请注意，该模式不是从根部开始，而是从左侧开始(在本例中)。它也可能以 right 开头，但总是以 root 结尾。

Answer 1

您要求的是修改后的深度优先遍历，其中仅在 1) 节点是叶节点或 2) 节点位于树的“外部路径”时才打印/返回节点的值，其中“外部路径”定义为

如果您通过从根开始的所有左(或右)路径到达该节点，或者如果该节点是父节点的右(或左)子节点，则该节点是“外部路径”的一部分本身是“外部路径”一部分但没有左(或右)子节点的节点。

如果您知道如何编写 DFS，那么可以通过在遍历过程中检查一些额外的条件来实现此处的修改。