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

关注
发布于: 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
﻿
                                                欢迎关注公众号 大话算法，收看更多精彩内容
﻿