GoJava算法之二叉树的所有路径示例详解

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《GoJava算法之二叉树的所有路径示例详解》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下算法、Java、二叉树路径，希望所有认真读完的童鞋们，都有实质性的提高。

二叉树的所有路径

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

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

• 示例 1：

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

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

• 示例 2：

输入：root = [1]

输出：["1"]  

提示：

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

-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);
            }
        }
    }
}
</string></string></string></string>

时间复杂度：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 " + 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
}

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

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

到这里，我们也就讲完了《GoJava算法之二叉树的所有路径示例详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！