写点什么

图解面试题 - 二叉树的所有路径

用户头像
9527
关注
发布于: 2020 年 10 月 15 日
图解面试题-二叉树的所有路径

题目描述

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   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 re



迭代实现

我们也可以使用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



欢迎关注公众号 大话算法,收看更多精彩内容



发布于: 2020 年 10 月 15 日阅读数: 36
用户头像

9527

关注

公众号:大话算法 2017.12.14 加入

图解各种算法

评论

发布
暂无评论
图解面试题-二叉树的所有路径