【二叉树类算法题】二叉树的所有路径
题目描述
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1 / \ 2 3 \ 5
输出:
["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
DFS实现
要求从根节点到叶子节点的路径,最适合干这件事情的就是DFS(Depth First Search 深度优先搜索)。
DFS的特点就是一竿子插到底
具体实现思路是这样:
首先初始化临时路径为空“”
之后每下降一层,就将临时路径跟当前节点的值拼接上
对于任何一个节点,要不就是叶子节点,要不就是非叶子节点,我们可以这样处理:
-
如果当前节点如果是叶子节点,那么拼接的内容是
root.val
-
如果当前节点不是叶子节点,那么拼接的内容是
root.val+"->"
完整的执行过程如下图:
时间复杂度:O(N^2)
空间复杂度:O(N^2)
java代码:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) {
return new ArrayList<String>();
}
List<String> res = new ArrayList<String>();
dfs(root,"",res);
return res;
}
private void dfs(TreeNode root, String tmp, List<String> res) {
if(root==null) {
return;
}
//如果是叶子节点,将 root.val 拼接到临时路径中
if(root!=null && (root.left==null && root.right==null)) {
res.add(tmp+root.val);
return;
}
//如果当前节点不是叶子节点,将 root.val+"->" 拼接到临时路径中
if(root.left!=null) {
dfs(root.left,tmp+root.val+"->",res);
}
//如果当前节点不是叶子节点,将 root.val+"->" 拼接到临时路径中
if(root.right!=null) {
dfs(root.right,tmp+root.val+"->",res);
}
}
}
python代码:
class Solution(object):
def binaryTreePaths(self, root):
if not root:
return []
res = []
def dfs(root,tmp):
if not root:
return
# 如果是叶子节点,将 root.val 拼接到临时路径中
if root and not (root.left or root.right):
res.append(tmp+str(root.val))
return
# 如果当前节点不是叶子节点,将 root.val+"->" 拼接到临时路径中
if root.left:
dfs(root.left,tmp+str(root.val)+"->")
# 如果当前节点不是叶子节点,将 root.val+"->" 拼接到临时路径中
if root.right:
dfs(root.right,tmp+str(root.val)+"->")
dfs(root,"")
return res
迭代实现
我们也可以使用BFS(Breadth First Search 宽度优先搜索算法)来完成这道
我们来看下详细的执行过程:
首先是初始化,将【根节点1,""】放入到队列中
第二步,从队列中弹出【1,""】,1
不是叶子节点,且1
有左节点,于是将左节点以及拼接的"1->"放入队列中1
也有右节点,再将右节点以及拼接的"1->"放入队列中
此时队列中就有两个元素【2,"1->"】,【3,"1->"】
第三步,从队列中弹出【2,"1->"】,2
不是叶子节点2
有右节点,于是将右节点以及拼接的"1->2->"放入队列中
之后再弹出【3,"1->"】,由于3
是叶子节点,于是拼接成"1->3"
后,将其放入到最终结果集中
第四步,从队列中弹出【5,"1->2->"】,由于5
是叶子节点,于是拼接成"1->2->5"
后,将其放入到最终结果集中
完整的执行过程如下图:
时间复杂度:O(N^2)
空间复杂度:O(N^2)
java代码:
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) {
return new ArrayList<String>();
}
//res是最终结果集,queue中存放的是封装的Pair对象
List<String> res = new ArrayList<String>();
Queue<Pair> queue = new LinkedList<Pair>();
queue.offer(new Pair(root,""));
while(!queue.isEmpty()) {
Pair p = queue.poll();
String path = p.path;
TreeNode node = p.node;
if(node==null) {
continue;
}
//如果当前节点是叶子节点,将其拼装后放入最终结果集中
if(node!=null && (node.left==null && node.right==null)) {
res.add(path+node.val);
continue;
}
//如果当前节点不是叶子节点,将其左子树和新路径放入队列中
if(node.left!=null) {
queue.offer(new Pair(node.left,path+node.val+"->"));
}
//如果当前节点不是叶子节点,将其右子树和新路径放入队列中
if(node.right!=null) {
queue.offer(new Pair(node.right,path+node.val+"->"));
}
}
return res;
}
//自定义一个Pair对象,封装TreeNode和临时路径Path
class Pair {
private TreeNode node;
private String path;
Pair(TreeNode node,String path) {
this.node = node;
this.path = path;
}
}
}
python代码:
class Solution(object):
def binaryTreePaths(self, root):
if not root:
return []
# res是最终结果集,queue中存放的是封装的[节点,临时路径]
res = []
queue = [[root,""]]
while queue:
node,tmp = queue.pop(0)
if not node:
continue
# 如果当前节点是叶子节点,将其拼装后放入最终结果集中
if node and not (node.left or node.right):
res.append(tmp+str(node.val))
continue
# 如果当前节点不是叶子节点,将其左子树和新路径放入队列中
if node.left:
queue.append( [node.left,tmp+str(node.val)+"->"] )
# 如果当前节点不是叶子节点,将其右子树和新路径放入队列中
if node.right:
queue.append( [node.right,tmp+str(node.val)+"->"] )
return res
本文地址:https://blog.csdn.net/hixiaoxiaoniao/article/details/109033299