2

二叉树的所有路径

 1 year ago
source link: https://helloteemo.github.io/2022/11/17/leetcode/%E6%A0%91/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文最后更新于：2022年11月30日 晚上

二叉树的所有路径

跳转链接

二叉树的所有路径

二叉树的所有路径

二叉树的所有路径

二叉树的解题思路：

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

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

image-20221117163806253

image-20221117163806253

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

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

我们想象一下只有三个节点如何获取所有路径呢？拿根节点加上左右节点的所有路径就可以啦，也就是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
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK