Go Java算法二叉树所有路径

黄丫丫 2022-09-28 我要评论

二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]

输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]

输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内

-100 <= Node.val <= 100

方法一：深度优先遍历搜索（Java）

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。

如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

递归二步曲：

(1) 找出重复的子问题。

前序遍历的顺序是：根节点、左子树、右子树。
在本题同样也是这个顺序：将根节点加入路径，递归左子树，递归右子树。
对于左子树和右子树来说，也都是同样的操作。

(2) 确定终止条件。

对于二叉树的所有路径中的每条路径，当遍历到叶子节点的时候为当前路径的结束。并且将当前路径加入结果集。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }
    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

时间复杂度：O（N^2）

空间复杂度：O（N^2）

方法二：广度优先遍历（Go）

我们也可以用广度优先搜索来实现。

我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。
在每一步迭代中，我们取出队列中的首节点
如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。
当队列为空时广度优先搜索结束

func binaryTreePaths(root *TreeNode) []string {
    paths := []string{}
    if root == nil {
        return paths
    }
    nodeQueue := []*TreeNode{}
    pathQueue := []string{}
    nodeQueue = append(nodeQueue, root)
    pathQueue = append(pathQueue, strconv.Itoa(root.Val))
    for i := 0; i < len(nodeQueue); i++ {
        node, path := nodeQueue[i], pathQueue[i]
        if node.Left == nil && node.Right == nil {
            paths = append(paths, path)
            continue
        }
        if node.Left != nil {
            nodeQueue = append(nodeQueue, node.Left)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Left.Val))
        }
        if node.Right != nil {
            nodeQueue = append(nodeQueue, node.Right)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Right.Val))
        }
    }
    return paths
}