「力扣」第 257 题:二叉树的所有路径
传送门:257. 二叉树的所有路径。
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
要求:给定一棵二叉树,返回所有表示从根结点到叶子结点路径的字符串。
关键:理解“回溯”在深度优先搜索里面的应用。
思路1:使用递归完成,中途记录路径,走到叶子结点的时候结算;
Python 代码:特别注意:通过参数传递的方式,就没有显式的回溯的过程了。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 257. 二叉树的所有路径
# 给定一个二叉树,返回所有从根结点到叶子结点的路径。
class Solution:
# 深度优先遍历,我感觉最好理解
# 参考:https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return res
self.__helper(root, '', res)
return res
def __helper(self, node, pre, res):
if node.left is None and node.right is None:
res.append(pre + str(node.val))
return
# 特别注意:通过参数传递的方式,就没有显式的回溯的过程了
if node.left:
self.__helper(node.left, pre + str(node.val) + '->', res)
if node.right:
self.__helper(node.right, pre + str(node.val) + '->', res)
思路2:使用深度优先遍历,回溯的方式,一定要记住:一条路径走完以后,要弹出栈。
Python 代码:
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return res
path = []
self.__helper(root, path, res)
return res
def __helper(self, node, path, res):
"""
:param node:
:param path: 沿途经过的结点值组成的列表
:param res: 存放最终结果的变量
:return:
"""
if node is None:
return
path.append(str(node.val))
if node.left is None and node.right is None:
# 可以结算了
res.append("->".join(path))
return
if node.left:
self.__helper(node.left, path, res)
# 【重点】:回溯的时候,要记得弹出
# 左边结点都看过了,所以 path 要弹出
path.pop()
if node.right:
self.__helper(node.right, path, res)
# 【重点】:回溯的时候,要记得弹出
# 右边结点都看过了,所以 path 要弹出
path.pop()
以上两种方法都使用了辅助函数,其实还可以不借助辅助函数,直接在原来的函数上做递归。
Python 代码:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root is None:
return []
if root.left is None and root.right is None:
res.append(str(root.val))
return res
left_paths = self.binaryTreePaths(root.left)
for lpath in left_paths:
res.append(str(root.val) + '->' + lpath)
right_paths = self.binaryTreePaths(root.right)
for rpath in right_paths:
res.append(str(root.val) + '->' + rpath)
return res
我写的题解地址:
# 参考:https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines
LeetCode 第 257 题:二叉树的所有路径
给定一个二叉树,返回所有从根结点到叶子结点的路径。
Python 代码:使用递归完成,中途记录路径,走到叶子结点的时候结算; 特别注意:通过参数传递的方式,就没有显式的回溯的过程了。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def binaryTreePaths(self, root):
res = []
if root is None:
return res
self.__helper(root, '', res)
return res
def __helper(self, node, pre, res):
if node.left is None and node.right is None:
res.append(pre + str(node.val))
return
# 特别注意:通过参数传递的方式,就没有显式的回溯的过程了
if node.left:
self.__helper(node.left, pre + str(node.val) + '->', res)
if node.right:
self.__helper(node.right, pre + str(node.val) + '->', res)
Python 代码:使用深度优先遍历,回溯的方式,一定要记住:一条路径走完以后,要弹出栈。
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def binaryTreePaths(self, root):
res = []
if root is None:
return res
path = []
self.__helper(root, path, res)
return res
def __helper(self, node, path, res):
if node is None:
return
path.append(str(node.val))
if node.left is None and node.right is None:
res.append("->".join(path))
# 注意:这里不能 return
# 因为 path 里的内容还要弹出
# return
if node.left:
self.__helper(node.left, path, res)
if node.right:
self.__helper(node.right, path, res)
path.pop()
LeetCode 第 257 题:得到二叉树的所有路径。
给定一个二叉树,返回所有从根节点到叶子节点的路径。
传送门:https://leetcode.com/problems/binary-tree-paths/description/
分析:典型的回溯。下面的这个写法比较奇怪。
Java 代码:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
// 这个节点是个根节点,想一想只有一个元素的情况
if (root.left == null && root.right == null) {
res.add(String.valueOf(root.val));
}
List<String> leftS = binaryTreePaths(root.left);
for (int i = 0; i < leftS.size(); i++) {
res.add(String.valueOf(root.val) + "->" + leftS.get(i));
}
List<String> rightS = binaryTreePaths(root.right);
for (int i = 0; i < rightS.size(); i++) {
res.add(String.valueOf(root.val) + "->" + rightS.get(i));
}
return res;
}
}
心得:分析递归关系是这道题的难点。