257. 二叉树的所有路径

Difficulty
easy
Tags
二叉树
回溯
URL
https://leetcode-cn.com/problems/binary-tree-paths/
Star
❤
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:

   1
 /   \
2     3
 \
  5

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

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

法1 回溯法

思路
递归的遍历节点。并且在访问每个节点时都判断是否为叶子节点。
回溯采用正宗的回溯模板即可
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def __init__(self):
        self.result = []
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return self.result
        path = []
        path.append(root.val)    # 做选择 这个选择不用撤销！！
        self.backtrack(node=root, path=path)
        return self.result
    def backtrack(self, node, path):
        # 终止条件
        if node.left is None and node.right is None:
            temp_str = ""
            for i in range(len(path)-1):
                temp_str += str(path[i]) + "->"
            temp_str += str(path[-1])
            self.result.append(temp_str)
            return 
        # 做选择 最多有两个选择 左节点 和 右节点
        if node.left is not None:
            path.append(node.left.val)  # 做选择
            self.backtrack(node.left, path)
            path.pop() # 撤销选择
        if node.right is not None:
            path.append(node.right.val)  # 做选择
            self.backtrack(node.right, path)
            path.pop() # 撤销选择
对上述代码的优化
本质上还是回溯，只是没有采用显式的回溯，而是将 path + "->" + str(node.left.val)作为参数传递给下一层，这样该层的path还是没有改变，所以不用撤销选择，且不用显式的做选择，因为参数已经包含了选择
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = []
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return self.result
        self.backtrack(node=root, path=str(root.val))
        return self.result
    

    def backtrack(self, node, path):
        if node.left is None and node.right is None:
            self.result.append(path)
        if node.left:
            self.backtrack(node.left, path + "->" + str(node.left.val))
        if node.right:
            self.backtrack(node.right, path + "->" + str(node.right.val))

法2 迭代法

思路
借助栈or队列遍历所有节点，在遍历的过程中，将某一节点压入栈中时，将 从根节点到该节点的路径 压入另外一个栈。具体来看，构建两个栈（或者队列），分别为tree_S,path_S 。 tree_Q用来存放节点，path_S用来存放路径。这样在从栈tree_Q中取出节点的时候，就可以把从根节点到该节点的路径也取出来，再去判断该节点是否为叶子节点，如果是叶子节点，就将该路径添加到result中。如果不是叶子节点，将该节点的左右节点入栈tree_S，同时将该节点的路径上新增左右节点的值加到path_S中。
💡
迭代法采用先序遍历，因为要先判断该节点是否为叶子节点，再去访问左右子树节点，这样才能形成父子路径关系
本质上就是对二叉树的一个遍历，只不过遍历的时候新加了以下两条：
  • 遍历过的每一个节点，都把 到该节点的路径 存起来，且要和该节点对应起来
  • 对每个节点判断 是否为叶节点，如果是叶节点，就把 到该节点的路径放到result
题解
用队列实现(宽度优先搜索)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = []
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return self.result
        # 建立两个队列
        tree_Q = []
        path_Q = []
        # 将跟节点入队
        tree_Q.append(root)
        path_Q.append([root.val])
        while len(tree_Q) > 0:
            # 每次循环 从队列中取出一个节点node  和 到该节点的路径path
            node = tree_Q.pop(0)
            path = path_Q.pop(0)
            # 该节点为叶子节点，则将路径path加到result中
            if node.left is None and node.right is None:
                temp  =''
                for i in range(len(path)-1):
                    temp += str(path[i]) + '->'
                temp += str(path[-1])
                self.result.append(temp)
            # node不是叶子节点 ,去遍历左右子树，
						# 同时分别更新path(在node的path上新增左右节点的值)，并随左右子节点加入队列
            if node.left is not None:
                tree_Q.append(node.left)
                path_Q.append(path+[node.left.val])
            if node.right is not None:
                tree_Q.append(node.right)
                path_Q.append(path+[node.right.val])
        return self.result
用栈实现 （深度优先搜索）
和用队列实现的区别：
  • 一个是栈，一个是队列。注意操作pop(0) 和pop()
  • 一般而言，栈先访问右节点，队列先访问左节点
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = []
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return self.result
        # 建立两个栈
        tree_S = []
        path_S = []
        # 将跟节点入队
        tree_S.append(root)
        path_S.append([root.val])
        while len(tree_S) > 0:
            # 每次循环 从栈中取出一个节点node  和 到该节点的路径path
            node = tree_S.pop()
            path = path_S.pop()
            # 该节点为叶子节点，则将路径path加到result中
            if node.left is None and node.right is None:
                temp  =''
                for i in range(len(path)-1):
                    temp += str(path[i]) + '->'
                temp += str(path[-1])
                self.result.append(temp)
            # node不是叶子节点 ,去遍历左右子树，
            # 同时分别更新path(在node的path上新增左右节点的值)，并随左右子节点加入栈
            if node.right is not None:
                tree_S.append(node.right)
                path_S.append(path+[node.right.val])
            if node.left is not None:
                tree_S.append(node.left)
                path_S.append(path+[node.left.val])
        return self.result
上述两种方法基本一样，都是采用两个同步的队列/栈 来存放 节点 和 对应的路径。可以优化的地方：
  • 采用一个队列/栈 ，因为对节点和路径 的操作都是同步的，所以可以采用一个队列/栈
  • 对路径的存放可以优化的地方。现在路径是通过列表来存放，就是说 路径栈 是个二维列表。里面的每一个元素都是这样一个[3,4,5]路径。可以将路径改为字符串“3->4->5”。具体存的时候，跟节点只存值val，后面每次更新path 都存 "->" + str(node.val)
优化代码如下
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = []
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        if root is None:
            return self.result
        # 新建立一个栈，并将首节点和首节点路径放进去
        stack = []
        stack.append(root)
        stack.append(str(root.val))
        while len(stack) > 0:
            path = stack.pop()
            node = stack.pop()
            if node.left is None and node.right is None:
                self.result.append(path)
            if node.left:
                stack.append(node.left)
                stack.append(path + "->" + str(node.left.val))
            if node.right:
                stack.append(node.right)
                stack.append(path + "->" + str(node.right.val))
        return self.result