İkili Ağac Ən Uzun Ardıcıl Ardıcıllıq LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon ByteDance Facebook google PinterestBaxılıb 24

Problem bəyanat

Binary Tree Ən Uzun Ardıcıl Ardıcıllıq LeetCode Həlli – Nəzərə alınmaqla root ikili ağacın qaytarılması ən uzun ardıcıl yolun uzunluğu.

Yol, valideyn-uşaq əlaqələri ilə yanaşı, bəzi başlanğıc qovşağından ağacdakı hər hansı qovşaqdakı istənilən qovşaq ardıcıllığına aiddir. Ən uzun ardıcıl yol valideyndən uşağa olmalıdır (əks ola bilməz).

İkili Ağac Ən Uzun Ardıcıl Ardıcıllıq LeetCode HəlliPin

 

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation:

Ən uzun ardıcıl

 sequence path is 3-4-5, so return 3.

İkili Ağacın Ən Uzun Ardıcıl Ardıcıllığının İzahı

Sadəcə çox intuitiv dərinlik-ilk axtarış, cur node dəyərini növbəti səviyyəyə göndərin və onu növbəti səviyyə qovşağı ilə müqayisə edin.

İkili Ağacın Ən Uzun Ardıcıl Ardıcıllığı üçün kod LeetCode Həlli

C ++ kodu

class Solution {
public:
    int longestConsecutive(TreeNode* root) {
        return search(root, nullptr, 0);
    }
    
    int search(TreeNode *root, TreeNode *parent, int len) {
        if (!root) return len;
        len = (parent && root->val == parent->val + 1)?len+1:1;
        return max(len, max(search(root->left, root, len), search(root->right, root, len)));
    }
};

Java kodu

public class Solution {
    private int max = 0;
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        helper(root, 0, root.val);
        return max;
    }
    
    public void helper(TreeNode root, int cur, int target){
        if(root == null) return;
        if(root.val == target) cur++;
        else cur = 1;
        max = Math.max(cur, max);
        helper(root.left, cur, root.val + 1);
        helper(root.right, cur, root.val + 1);
    }
}

Python kodu

class Solution:
     def longestConsecutive(self, root: TreeNode) -> int:
        def longest_path(root):
            if not root:
                return 0
            length = 1
            l = longest_path(root.left)
            r = longest_path(root.right)
            if root.left and root.left.val == root.val + 1:
                length = max(length, 1 + l)
            if root.right and root.right.val == root.val + 1:
                length = max(length, 1 + r)
            res[0] = max(res[0], length)
            return length
        
        res = [0]
        longest_path(root)
        return res[0]

İkili Ağacın Ən Uzun Ardıcıl Ardıcıllığı üçün Mürəkkəblik Təhlili

Zaman Mürəkkəbliyi: n qovşağı olan ikili ağacın O(n) DFS keçidi O(n) vaxtını alır.

Məkan Mürəkkəbliyi: O(1) heç bir əlavə yer istifadə edilmir.

Referans: https://en.wikipedia.org/wiki/Depth-first_search

Şərh yaz

Translate »