LeetCode-樹-Hard

記錄了初步解題思路以及本地實作代碼；并不一定為最優也希望大家能一起探讨一起進步

- - 297. Serialize and Deserialize Binary Tree 二叉樹的序列化與反序列化
  - 685. Redundant Connection II 備援連接配接 II
  - 834. Sum of Distances in Tree 樹中距離之和
  - 968. Binary Tree Cameras 監控二叉樹
  - 1028. Recover a Tree From Preorder Traversal 從先序周遊還原二叉樹

297. Serialize and Deserialize Binary Tree 二叉樹的序列化與反序列化

序列化反序列化都使用list來存放node

反序列化注意list範圍

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        l=[root]
        ret=[]
        while len(l)>0:
            tmp = l.pop(0)
            if tmp==None:
                ret.append("null")
                continue
            ret.append(tmp.val)
            left,right = tmp.left,tmp.right
            l.append(left)
            l.append(right)
        for i in range(len(ret)-1,-1,-1):
            if ret[i]!="null":
                return ret[:i+1]
            
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return
        root = TreeNode(data[0])
        l = [root]
        i=1
        while len(l)>0:
            tmp = l.pop(0)
            if tmp==None or i>=len(data):
                continue
            tmp.left = None if data[i]=="null" else TreeNode(data[i])
            if i+1<len(data):
                tmp.right = None if data[i+1]=="null" else TreeNode(data[i+1])
            else:
                tmp.right = None
            i+=2
            l.append(tmp.left)
            l.append(tmp.right)
        
        return root

685. Redundant Connection II 備援連接配接 II

check用來檢查是否滿足

1.入度不能有大于1的

2.不能存在圈

先将所有點的父節點取出，如果存在有兩個父節點那麼說明這個節點需要取出一條邊周遊後check是否正确若正确将結果暫存ret

判斷ret,

若ret内有多個則取出位置最靠後的作為結果

若ret==0:

所有節點入度都正常說明存在圈從後往前去除一個點 check是否正常若正常則答案為這個點

def findRedundantDirectedConnection(edges):
    """
    :type edges: List[List[int]]
    :rtype: List[int]
    """
    dic={}
    ans=[]
    ret =[]
    def check(l):
        #入度不能大于1
        endpoint = [y for x,y in l]
        if len(endpoint)!=len(set(endpoint)):
            return False

        def find(p,x):
            while p[x] != x:
                p[x] = p[p[x]]
                x = p[x]
            return p[x]

        # 判斷給定的圖是不是有圈
        def cycle(graph):
            p = {}
            for a, b in graph:
                p.setdefault(a, a)
                p.setdefault(b, b)
                pa, pb = find(p, a), find(p, b)
                if pa == pb: 
                    return(True)
                else:
                    p[pa] = p[pb]
                    
        if cycle(l):
            return False
            
        return True
    
    for v in edges:
        top = v[0]
        end = v[1]
        dic.setdefault(end,[])
        dic[end].append(top)
            
    for k in dic.keys():
        if len(dic[k])>1:
            for v in dic[k]:
                ori = edges[:]
                tmp=[v,k]
                ori.pop(ori.index(tmp))
                if check(ori):
                    ret.append(tmp)
    
    if len(ret)==0:
        for i in range(len(edges)-1,-1,-1):
            ori = edges[:]
            ori.pop(i)
            if check(ori):
                ans = edges[i]
                break
    else:
        pos = -1
        for i in ret:
            if edges.index(i)>pos:
                pos = edges.index(i)
                ans = i    
    
    return ans
    


def find(p,x):
    while p[x] != x:
        p[x] = p[p[x]]
        x = p[x]
    return p[x]
        # 判斷給定的圖是不是有圈
def cycle(graph):
    p = {}
    for a, b in graph:
       
        p.setdefault(a, a)
        p.setdefault(b, b)
        pa, pb = find(p, a), find(p, b)
        print([a,b],p,pa,pb)
        if pa == pb: 
            return(True)
        else:
            p[pa] = p[pb]

834. Sum of Distances in Tree 樹中距離之和

使用count[n]記錄某一節點n的子節點包含自己

使用res[n]記錄節點n到各個不同節點的距離

若有[a,b] a為根節點 b為子節點

求根節點a時：

對于count的計算：

count[a]+=count[b]

對于res的計算：

b的所有節點count(b)從b到a 距離都增加了1 是以從b到a總共增加了count(b)*1

res[a] += res[b]+count[b]

求子節點b時：

對于res的計算：

同樣從a到b有count[b]個節點距離減少了1 而有N-count[b]個節點距離增加了1

是以：

res[b] = res[a]- count[b] + (N-count[b])

def sumOfDistancesInTree(N, edges):
    """
    :type N: int
    :type edges: List[List[int]]
    :rtype: List[int]
    """
    from collections import defaultdict
    tree = defaultdict(set)
    for x,y in edges:
        tree[x].add(y)
        tree[y].add(x)
    
    count = [1 for i in range(N)]
    ret = [0 for i in range(N)]
        
    def dfs(root,visit):
        visit.add(root)
        for i in tree[root]:
            if i not in visit:
                dfs(i,visit)
                count[root] += count[i]
                ret[root] += ret[i] + count[i]
                
    def dfs2(root,visit):
        visit.add(root)
        for i in tree[root]:
            if i not in visit:
                ret[i] = ret[root]-count[i]+N-count[i]
                dfs2(i,visit)
    dfs(0,set())
    dfs2(0,set())
    return ret

968. Binary Tree Cameras 監控二叉樹

每個節點有三種狀态：

1：可以觀察到

2：不可以觀察到

3：安裝了攝像頭

對樹進行dfs從葉節點開始往上分析

若節點的左右節點存在不可觀測到的點（2）則該節點需要安裝攝像頭 ret+=1 傳回該節點的狀态3

若節點的左右節點存在安裝攝像頭的點（3）則該節點可以被觀察到傳回狀态1

否則該節點無法被觀察到傳回 2

對根節點開始分析dfs(root) 傳回根節點的狀态如果這個狀态==2 則需要在root上安裝 ret+=1

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def minCameraCover(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    ret = 0
    
    def dfs(node):
        if not node:
            return 1
        left,right = dfs(node.left),dfs(node.right)
        if left==2 or right==2:
            ret=ret+1
            return 3
        elif left==3 or right==3:
            return 1
        else:
            return 2
    if dfs(root)==2:
        ret+=1
    return ret

1028. Recover a Tree From Preorder Traversal 從先序周遊還原二叉樹

1.遞歸

check:

用來傳回“-”的個數ans 以及這個數值v ans就是這個v應該在的層數level

do:

用來添加節點

如果節點的dot=ans 及應該在的層數與目前的層數level相等則生成tmp節點

這個是該node節點的左子節點

再對這個左節點進行分析

do 傳回生成的節點以及該節點的層數tmpdot

若tmpdot與level相等則該節點為node的右節點

否則将節點tmp 以及其層數tmpdot 傳回

2.使用stack解題

先對S進行初步處理：

在list中存放(x,level) x為值 level表示這個值應該在的層數

周遊list：

對于節點node stack記憶體放node上層的節點若存在層數與node相同或更下層的則這些節點将不會再使用到 pop出stack中

此時 stack中的末節點及該node節點的父節點 parent

若parent已有左節點則node放至右邊否則 node為左節點

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def recoverFromPreorder(self,S):
        """
        :type S: str
        :rtype: TreeNode
        """
        self.S=S
        
        def check():
            ans = 0
            v=""
            if len(self.S)==0:
                return 0,0
            while self.S[0]=="-":
                ans+=1
                self.S = self.S[1:]
            
            while len(self.S)>0 and self.S[0]!="-":
                v += self.S[0]
                self.S = self.S[1:]
            return ans,v
        
        if self.S[0]=="-":
            return 
        v=""
        while len(self.S)>0 and self.S[0]!="-":
            v += self.S[0]
            self.S = self.S[1:]
        root = TreeNode(v)
        if len(self.S)==0:
            return root
        self.S=self.S[1:]
        
        def do(node,level):
            dot,v = check()
            print("40",dot,v,level)
            tmp = TreeNode(v)
            if dot==level:
                node.left =tmp
                tmp,tmpdot = do(node.left,level+1)
                print(tmpdot,tmp.val,level)
                if tmpdot==level:
                    node.right = tmp
                    tmp,tmpdot = do(node.right,level+1)
                return tmp,tmpdot
            return tmp,dot 
            
        do(root,1)
        return root
    
    def recoverFromPreorder2(self,S):
        """
        :type S: str
        :rtype: TreeNode
        """
        s = S.split('-')
        level = 0
        l = list()
        for x in s:
            if x:
                l.append((x, level))
                level = 1
            else:
                level += 1
        root = TreeNode(None)
        stack = [(root,-1)]
        for value, depth in l:
            while depth <= stack[-1][1]:
                stack.pop()
            node = TreeNode(value)
            parent = stack[-1][0]
            stack.append((node, depth))
            if parent.left:
                parent.right = node
            else:
                parent.left = node
        return root.left

LeetCode-樹-Hard

目錄

297. Serialize and Deserialize Binary Tree 二叉樹的序列化與反序列化

685. Redundant Connection II 備援連接配接 II

834. Sum of Distances in Tree 樹中距離之和

968. Binary Tree Cameras 監控二叉樹

1028. Recover a Tree From Preorder Traversal 從先序周遊還原二叉樹

繼續閱讀

Common Questions Of Gtk+

求水窪的問題——深度優先算法

200. 島嶼的個數（深度優先搜尋）

dfs深度優先搜尋_圖的深度優先搜尋（DFS）

【算法提高班】貪婪政策

#每日一題力扣第28題采購方案

【python】：布爾運算

studio📍位址：15RegentStreetWoolloongabba,Brisbane,Queensland410

對角線周遊LeetCode–對角線周遊

DOS常用指令的使用

查找算法之二分查找查找算法之二分查找

LeetCode-110-平衡二叉樹-C語言

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

LeetCode OJ Binary Tree Right Side View

leetcode809