【二叉树类算法题】二叉树的所有路径
题目描述
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
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