[Leetcode] Binary Tree Paths 二叉树路径

Vicky 发布于2019-08-14 16:10 / 2021人阅读

摘要：递归法复杂度时间空间递归栈空间对于二叉树思路简单的二叉树遍历，遍历的过程中记录之前的路径，一旦遍历到叶子节点便将该路径加入结果中。当遇到最小公共祖先的时候便合并路径。需要注意的是，我们要多带带处理目标节点自身是最小公共祖先的情况。

Root To Leaf Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

递归法 复杂度

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间对于二叉树b=2

思路

简单的二叉树遍历，遍历的过程中记录之前的路径，一旦遍历到叶子节点便将该路径加入结果中。

代码

public class Solution {
    
    List res = new ArrayList();
    
    public List binaryTreePaths(TreeNode root) {
        if(root != null) findPaths(root,String.valueOf(root.val));
        return res;
    }
    
    private void findPaths(TreeNode n, String path){
        if(n.left == null && n.right == null) res.add(path);
        if(n.left != null) findPaths(n.left, path+"->"+n.left.val);
        if(n.right != null) findPaths(n.right, path+"->"+n.right.val);
    }
}

2018/2

class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        result = []
        if root is None:
            return result
        self.findPaths(root, [], result)
        return result
        
    def findPaths(self, node, path, result):
        path.append(str(node.val))
        if node.left is not None:
            self.findPaths(node.left, path, result)
        if node.right is not None:
            self.findPaths(node.right, path, result)
        if node.left is None and node.right is None:
            result.append("->".join(path))
        path.pop()

Node to Node Binary Tree Path

给定一棵二叉树的根节点和两个任意节点，返回这两个节点之间的最短路径

深度优先标记 复杂度

时间 O(h) 空间 O(h) 递归栈空间

思路

两个节点之间的最短路径一定会经过两个节点的最小公共祖先，所以我们可以用LCA的解法。不同于LCA的是，我们返回不只是标记，而要返回从目标结点递归回当前节点的路径。当遇到最小公共祖先的时候便合并路径。需要注意的是，我们要多带带处理目标节点自身是最小公共祖先的情况。

代码

public LinkedList helper(TreeNode n, TreeNode p, TreeNode q){
    if(n == null){
        return null;
    }
    
    LinkedList left = helper(n.left, p, q);
    LinkedList right = helper(n.right, p, q);
    
    // 当左右都为空时
    if(left == null && right == null){
        // 如果当前节点是目标节点，开启一条新路径
        if(n == p || n == q){
            LinkedList l = new LinkedList();
            l.add(n);
            return l;
        } else {
        // 否则标记为空
            return null;
        }
    // 如果左右节点都不为空，说明是最小公共祖先节点，合并两条路径
    } else if(left != null && right != null){
        finalPath.addAll(left);
        finalPath.add(n);
        Collections.reverse(right);
        finalPath.addAll(right);
        return left;
    // 如果当前节点是目标结点，且某一个子树不为空时，说明最小公共祖先是节点自身
    } else if (left != null){
        left.add(n);
        if(n == p || n == q){
            finalPath.addAll(left);
        }
        return left;
    } else {
        right.add(n);
        if(n == p || n == q){
            finalPath.addAll(right);
        }
        return right;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree 二叉树 python二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66159.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[Leetcode] Path Sum I & II & III 路径和1,2,3

摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。最新更新请见：https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...

caiyongji 2019-08-14 12:25 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
[Leetcode] Binary Tree Maximum Path Sum 二叉树最大路径和

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。代码连接父节点的最大路径是一二四这三种情况的最大值当前节点的最大路径是一二三四这四种情况的最大值用当前最大来更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

魏宪会 2019-08-14 12:25 评论0 收藏0
LeetCode 之 JavaScript 解答第104题 —— 二叉树的最大深度

摘要：小鹿题目二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。求二叉树的深度，必然要用到递归来解决。分别递归左右子树。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿题目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 评论0 收藏0