查找二叉树中的所有路径

Question

我正在尝试解决“给定一棵二叉树，返回所有根到叶路径。”的编码问题。

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

我见过一种解决方案

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        allPath = []
        if root is None:
            return []
        self.find_all_paths_recursive(root, [], allPath)
        return allPath

    def find_all_paths_recursive(self, currNode, currPath, allPath):
        if currNode is None:
            return 
        currPath.append(currNode.val)
        if currNode.left is None and currNode.right is None:
            currOut = '->'.join([str(x) for x in list(currPath)])
            allPath.append(currOut)
        # traverse left sub tree
        self.find_all_paths_recursive(currNode.left, currPath, allPath)
        # traverse right sub tree
        self.find_all_paths_recursive(currNode.right, currPath, allPath)
        del currPath[-1]

运行上面的代码给我的答案是[“1->2->5”,“1->3”]，这是正确的。

我正在考虑将

if currNode.left is None and currNode.right is None:

下的代码块更改为

      if currNode.left is None and currNode.right is None:
            #currOut = '->'.join([str(x) for x in list(currPath)])
            #allPath.append(currOut)
            allPath.append(currPath)

应该给我结果 [[1,2,5], [1,3]]。然而，这个改变给我返回了结果[[],[]]。我想知道为什么这不起作用？

Answer 1

由于您想直接添加 currPath，因此必须立即添加 currPath 的副本。

像这样：

if currNode.left is None and currNode.right is None:
    #currOut = '->'.join([str(x) for x in list(currPath)])
    # allPath.append(currOut)
    allPath.append(list(currPath))

编辑：

如果不添加

list

，您会将原始列表对象添加到 allPath 中，该对象将由于递归而更新。添加

list

将生成

copy of the original list object

，它将被保存且不会进一步更新。

Answer 2

递归是函数式遗产，因此以函数式风格使用它会产生最佳结果。这意味着避免变量重新分配、其他突变和副作用。

让我们看看以这种方式实现

btree

会是什么样子。注意

node

属性

left

和

right

可以在构造新节点时设置 -

# btree.py

def empty():
  return None

class node:
  def __init__(self, val, left = empty(), right = empty()):
    self.val = val
    self.left = left
    self.right = right

def paths(t, p = ()):
  if not t:
    return
  elif t.left or t.right:
    yield from paths(t.left, (*p, t.val))
    yield from paths(t.right, (*p, t.val))
  else:
    yield "->".join(map(str, (*p, t.val)))

这是您的

main

计划 -

# main.py

from btree import node, empty, paths

#    1
#  /   \
# 2     3
#  \
#   5

t = node(1, node(2, empty(), node(5)), node(3))

print(list(paths(t)))

['1->2->5', '1->3']

Answer 3

您所需要的只是使用递归深度优先搜索算法。这是使用 Java 的解决方案：

class NodePrintAllPath {
    int data;
    NodePrintAllPath left, right;

    public NodePrintAllPath(final int value) {
        this.data = value;
        this.left = this.right = null;
    }
}


public class PrintAllPathOfBinaryTreeBFS {

    public static void  main(String[] args){
        NodePrintAllPath root = new NodePrintAllPath(10);
        root.left = new NodePrintAllPath(8);
        root.left.left = new NodePrintAllPath(3);
        root.left.right = new NodePrintAllPath(5);
        root.right = new NodePrintAllPath(2);
        root.right.left = new NodePrintAllPath(2);

        int[] path = new int[1000];
        printAllPathUsingDFS(root,path,0);


    }

    private static void printAllPathUsingDFS(NodePrintAllPath root, int[] path, int pathLength) {
        if(root == null){
            return;
        }

        path[pathLength] = root.data ;
        pathLength++;

        if(root.left == null && root.right == null){
            printPath(path,pathLength);
        }
        printAllPathUsingDFS(root.left, path,pathLength);
        printAllPathUsingDFS(root.right,path,pathLength);

    }

    private static void printPath(int[] path, int pathLength) {
        for(int i =0; i< pathLength; i++){
            System.out.print(path[i]+" ");
        }
        System.out.println("");
    }
}

//输出 10 8 3 10 8 5 10 2 2