成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Binary Tree Paths 二叉樹路徑

Vicky / 2071人閱讀

摘要：遞歸法復(fù)雜度時間空間遞歸?？臻g對于二叉樹思路簡單的二叉樹遍歷，遍歷的過程中記錄之前的路徑，一旦遍歷到葉子節(jié)點便將該路徑加入結(jié)果中。當遇到最小公共祖先的時候便合并路徑。需要注意的是，我們要多帶帶處理目標節(jié)點自身是最小公共祖先的情況。

Root To Leaf Binary Tree Paths 
Given a binary tree, return all root-to-leaf paths.
遞歸法 復(fù)雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸?？臻g 對于二叉樹b=2

思路

簡單的二叉樹遍歷，遍歷的過程中記錄之前的路徑，一旦遍歷到葉子節(jié)點便將該路徑加入結(jié)果中。

代碼 
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 
給定一棵二叉樹的根節(jié)點和兩個任意節(jié)點，返回這兩個節(jié)點之間的最短路徑
深度優(yōu)先標記 復(fù)雜度

時間 O(h) 空間 O(h) 遞歸?？臻g

思路

兩個節(jié)點之間的最短路徑一定會經(jīng)過兩個節(jié)點的最小公共祖先，所以我們可以用LCA的解法。不同于LCA的是，我們返回不只是標記，而要返回從目標結(jié)點遞歸回當前節(jié)點的路徑。當遇到最小公共祖先的時候便合并路徑。需要注意的是，我們要多帶帶處理目標節(jié)點自身是最小公共祖先的情況。

代碼 
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){
        // 如果當前節(jié)點是目標節(jié)點，開啟一條新路徑
        if(n == p || n == q){
            LinkedList l = new LinkedList();
            l.add(n);
            return l;
        } else {
        // 否則標記為空
            return null;
        }
    // 如果左右節(jié)點都不為空，說明是最小公共祖先節(jié)點，合并兩條路徑
    } else if(left != null && right != null){
        finalPath.addAll(left);
        finalPath.add(n);
        Collections.reverse(right);
        finalPath.addAll(right);
        return left;
    // 如果當前節(jié)點是目標結(jié)點，且某一個子樹不為空時，說明最小公共祖先是節(jié)點自身
    } 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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66159.html

相關(guān)文章

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • [Leetcode] Path Sum I & II & III 路徑和1,2,3

    摘要：只要我們能夠有一個以某一中間路徑和為的哈希表，就可以隨時判斷某一節(jié)點能否和之前路徑相加成為目標值。 最新更新請見：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 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • [Leetcode] Binary Tree Maximum Path Sum 二叉樹最大路徑和

    摘要：棧迭代復(fù)雜度時間空間遞歸?？臻g對于二叉樹思路首先我們分析一下對于指定某個節(jié)點為根時，最大的路徑和有可能是哪些情況。代碼連接父節(jié)點的最大路徑是一二四這三種情況的最大值當前節(jié)點的最大路徑是一二三四這四種情況的最大值用當前最大來更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

    魏憲會 評論0 收藏0

  • LeetCode 之 JavaScript 解答第104題 —— 二叉樹的最大深度

    摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿 題目：Maximum Depth of Binary Tre...

    boredream 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<