欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【二叉树类算法题】二叉树的所有路径

程序员文章站 2022-01-13 10:55:34
给定一个二叉树,返回所有从根节点到叶子节点的路径。...

题目描述

给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:

输入:

 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