每日一题

二叉树的所有路径

跳转链接

二叉树的所有路径

二叉树的解题思路：

1. 确定终止条件
2. 确定递归姿势
3. 递归条件

这里需要获取二叉树的所有路径，案例：

一个空节点的所有路径就是空的，而一个不存在子节点的节点的所有路径就是它自己。按照这个我们就可以确定终止条件了

因为是要获取二叉树的所有路径，那么肯定是先使用根节点了，所有使用的是前序遍历

我们想象一下只有三个节点如何获取所有路径呢？拿根节点加上左右节点的所有路径就可以啦，也就是1->2,1->3。这也就是它的递归条件

// 获取二叉树的所有路径，只需要把当前节点加上左右即可
func binaryTreePaths(root *TreeNode) []string {
    // 终止条件
    if root == nil {
		return nil
	}
	if root.Right == nil && root.Left == nil {
		return []string{strconv.Itoa(root.Val)}
	}

	// 使用当前节点
	var res = make([]string, 0, 2)
	// 左节点递归
	if root.Left != nil {
		treePaths := binaryTreePaths(root.Left)
		for _, path := range treePaths {
			res = append(res, fmt.Sprintf("%d->%s", root.Val, path))
		}
	}
    // 右节点递归
	if root.Right != nil {
		treePaths := binaryTreePaths(root.Right)
        // 拼接路径
		for _, path := range treePaths {
			res = append(res, fmt.Sprintf("%d->%s", root.Val, path))
		}
	}

	return res
}