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