当前位置:   article > 正文

Leetcode之二叉树_节点贡献度

节点贡献度

144.二叉树的前序遍历

遍历树的根节点,然后遍历树的左节点,然后遍历树的右节点。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(root):
            if not root:
                return None
            
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)

        dfs(root)
        return res
        
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

94.二叉树的中序遍历

先遍历树的左节点,然后遍历树的根节点,然后遍历树的右节点。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(root):
            if not root:
                return None
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        
        dfs(root)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

145.二叉树的后序遍历

先遍历树的左节点,然后遍历树的右节点,然后遍历树的根节点。

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(root):
            if not root:
                return None
            
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
           

        dfs(root)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

总结:
前中后,是指根的顺序——前中后。

102.二叉树的层序遍历
(1)将根节点加入到queue,遍历循环queue

(2)对当前queue的长度(该层节点的个数)执行:
把queue的最左边(按照先左后右的顺序)pop给r,将r的值保存在临时变量tmp中。

(3)如果存在r.left,queue加入r.left,如果存在r.root,queue加入r.root

(4)将整个tmp加入到res中

queue = collections.deque()
queue.popleft()

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        res = []
        queue = collections.deque()
        queue.append(root)

        while queue:
            size = len(queue)
            tmp = []
            for _ in range(size):
                r = queue.popleft()
                tmp.append(r.val)
                if r.left:
                   queue.append(r.left)
                if r.right:
                   queue.append(r.right)
            res.append(tmp)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

104.二叉树的最大深度
边界条件:叶节点,返回值为0
递归部分:max(左子树的深度,右子树的深度)+1

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
  • 1
  • 2
  • 3
  • 4
  • 5

543.二叉树的直径
深度优先搜索:
大多使用递归函数

递归函数三元素:
1.子问题与原问题做同样的事
2.需要有一个让递归结束的出口
3.递归表达式

叶节点的深度 = 1
节点的深度=max(左的深度,右的深度)+1

运用一个递归函数,计算每一个节点的左子节点的深度和右子节点的深度,再定义一个全局变量MAX,如果L+R>MAX,则更新L+R为最大的深度。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.Max = 0
        def depth(root):

            if not root:
                return 0
            L = depth(root.left)
            R = depth(root.right)

            if (L+R)>self.Max:
                self.Max = L+R
            return max(L,R)+1
        
        depth(root)
        return self.Max
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

544.平衡二叉树

同上,在计算二叉树左右节点的深度时,设置一个全局变量flag,当abs(L-R)>1时,flag=False

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        self.flag = True

        def depth(root):
            if not root:
                return 0

            L = depth(root.left)
            R = depth(root.right)

            if abs(L-R) > 1 :
                self.flag = False
            return max(L,R)+1

        depth(root)
        return self.flag
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

111.二叉树的最小深度

如果root是空节点,返回0
如果root的左节点或右节点为空,返回L+R+1
其余返回min(L,R)+1

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0 

        L = self.minDepth(root.left)
        R = self.minDepth(root.right)

        if L == 0 or R == 0:
            return L+R+1
        return min(L,R)+1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:return 0
        
        def dfs(root):
            if not root:return 0

            L = dfs(root.left)
            R = dfs(root.right)

            if not root.left or not root.right:
                return L+R+1
            else:
                return min(L,R)+1
        
        return dfs(root)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

404.左叶子之和
计算给定二叉树的所有左叶子之和。

注:一定是左叶子节点。

保证左子节点的左节点和右节点均为空

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:

        self.sum = 0
 
        def dfs(root):

            if not root:return

            dfs(root.left)
            dfs(root.right)

            if root.left and not root.left.left and not root.left.right:
                self.sum += root.left.val

        dfs(root)
        return self.sum

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

103.二叉树的锯齿层序遍历

注意函数:tmp.insert(0,r.val),可以在第0个位置插入r.val。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:return []
        res = []
        queue = collections.deque()
        queue.append(root)
        num = 0

        while queue:
            size = len(queue)
            tmp = []
            for _ in range(size):
                r = queue.popleft()
                if num % 2 == 0:
                    tmp.append(r.val)
                else:
                    tmp.insert(0,r.val)
                if r.left:
                        queue.append(r.left)
                if r.right:
                        queue.append(r.right)
                
            num += 1
            res.append(tmp)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

515.在每个树行中找最大值

对二叉树进行层序遍历,把每一层的数据保存在tmp中,再运用max(tmp)读取它的最大值。

class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        if not root:return []
        res = []
        queue = collections.deque()
        queue.append(root)

        while queue:
            size = len(queue)
            tmp =[]

            for _ in range(size):
                r = queue.popleft()
                tmp.append(r.val)

                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)

            res.append(max(tmp))
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

199.二叉树的右视图

对二叉树进行层序遍历,将每一层的数存储在tmp中,tmp.pop()弹出最右侧的数,添加到res中。

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:return []
        res = []
        queue = collections.deque()
        queue.append(root)

        while queue:

            tmp = []
            size = len(queue)

            for _ in range(size):

                r = queue.popleft()
                tmp.append(r.val)

                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            
            res.append(tmp.pop())
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

100.相同的树
对每一对p和q进行如下判断:
(1)如果p和q均为空,返回true(既是相对于整个树的根节点而言,又是对于叶节点而言)
(2)p和q有一个不为空,返回False
(3)如果p和q均不为空,比较p和q的值, 不一样则返回False,一样则进入下一轮迭代。

对以上过程进行迭代。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:return True
        elif not p or not q:return False
        elif p.val != q.val:
            return False
        
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

101.对称的二叉树

判断二叉树是否对称:
(1)root.left root.right均为空,True
(2)root.left 为空 root.right不为空, False
(3)root.right为空 root.left不为空 False
(4)root.left root.right均不为空:
判断left和right的值是否相等,递归调用(left.left,right.right)和(left.right,right.left)

要明确递归的部分是哪些,要对什么进行递归。

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:

        def fun(left,right):
            if left and not right:
                return False
            elif not left and right:
                return False
            elif not left and not left:
                return True
            else:
                return left.val == right.val and fun(left.left,right.right) and fun(left.right,right.left)
        
        if not root:
            return True
        flag = fun(root.left,root.right)
        return flag
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

662.二叉树的宽度

我定义了两个deque:queue和index_q。其中,queue用来存放元素,index_q用来存放元素的坐标。

采用了层序遍历的思想,将每一层的坐标存入到一个数组中,最后返回数组的最小值和最大值,宽度即为max(最大值-最小值+1)

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:return 0
        res = []
        queue = collections.deque()
        index_q = collections.deque()
        queue.append(root)
        index_q.append(1)

        while queue:
            size = len(queue)
            tmp = []

            for _ in range(size):
                r = queue.popleft()
                i = index_q.popleft()
                tmp.append(i)

                if r.left:
                    queue.append(r.left)
                    index_q.append(2*i)
                
                if r.right:
                    queue.append(r.right)
                    index_q.append(2*i+1)
                    
            res.append(max(tmp)-min(tmp)+1)
        return max(res)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

114.二叉树展开为链表

前序遍历+转换为链表
转换为链表的方式:
将前序遍历的结果输入到一个列表中,运用for循环逐个添加。

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        pre = list()

        def dfs(root):
            if not root:
                return
            pre.append(root)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        size = len(pre)
        for i in range(1,size):
            prev,curr = pre[i-1],pre[i]
            prev.left = None
            prev.right = curr
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

236.二叉树的最近公共祖先

(1)if not root:return root 和 if not root:return None是等价的
(2)执行L和R的过程中,如果全部得到返回值root(可能为p可能为q可能为None)将不会进行递归

L或R是空,说明该分支中不包含节点,因此返回另一个分支
如果L是空,返回R(此时的R代表p或者q)
如果R是空,返回L(此时的L代表p或者q)

如果都不为空,返回root(因为当前L和R均处于root的子节点下,所以此时的root即为公共节点)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        L = self.lowestCommonAncestor(root.left,p,q)
        R = self.lowestCommonAncestor(root.right,p,q)

        if not L:
            return R
        if not R:
            return L
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

通过递归对二叉树进行后序遍历,当遇到节点p或q时返回。从底至顶回溯,当节点p、q在节点root的异侧时,节点root即为最近公共祖先,则向上返回root。

112.路径总和

思路1:
dfs遍历二叉树,计算targetsum减去当前节点的值,如果是叶节点,则把当前的targetsum加入到一个数组res中。遍历数组,看是否有等于0的元素存在,若有则返回True。

思路2:
dfs遍历二叉树,计算targetsum减去当前节点的值,如果是叶节点,看当前节点的targetsum是否等于0,是0则返回True,不是0则返回False。
此外,到如果root为空,也返回False。
Left = dfs,Right = dfs
如果Left和Right中有一个为True,则返回True。

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        
        def dfs(root,targetSum):
            if not root:return False
            targetSum = targetSum - root.val
            if (root.left == None) and (root.right == None):
                return targetSum == 0

            Left = dfs(root.left,targetSum)
            Right = dfs(root.right,targetSum)
            return Left or Right
            
        return dfs(root,targetSum)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

113.路径总和2
要求返回路径的所有元素
路径:
用数组path来表示,每增加一个元素,则在末尾加上[root.val]

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        tmp = []
        res = []
        def dfs(root,targetSum,path):

            if not root:return
            targetSum = targetSum - root.val
 
            if (root.left == None) and (root.right == None):
                if targetSum == 0:
                    res.append(path+[root.val])

            dfs(root.left,targetSum,path+[root.val])
            dfs(root.right,targetSum,path+[root.val])
            
        path = []
        dfs(root,targetSum,path)
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

257.二叉树的所有路径
注意字符串的操作方式
定义空字符串’ ’
字符串添加数字时需要把数字转化为字符串的形式
注意 + ‘->’ 和数字一样。

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        res = []
        def dfs(root,path):
            if not root:return
            if root.left == None and root.right == None:
                res.append(path+str(root.val))
            dfs(root.left,path+str(root.val)+'->')
            dfs(root.right,path+str(root.val)+'->')

       
        dfs(root,'')
        return res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

437.路径总和3

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

在这里插入图片描述

用一个sumlist来存储上一节点的sumlist里面的值加上这一节点的值,末尾再加入这一节点的值。

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:

        def dfs(root,sumlist):
            if not root :return 0

            sumlist = [num+root.val for num in sumlist]
            sumlist.append(root.val)

            count = 0
            for num in sumlist:
                if num == targetSum:
                    count += 1

            return count + dfs(root.left,sumlist)+dfs(root.right,sumlist)
        
        return dfs(root,[])
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

124.二叉树中的最大路径和

思路:计算每个节点的贡献度。
贡献度 =max(max( 左子树的贡献度,右子树的贡献度),0)
最大路径和为左子树的贡献度+右子树的贡献度+节点的值

注意:⚠️递归只能出现一次!

如果子节点是空节点,计它的贡献度为0,如果节点的贡献度为负,也计它的贡献度为0.

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.Max = root.val
        def dfs(root):
            if not root : return 0

            Left = max(0,dfs(root.left))
            Right = max(0,dfs(root.right))

            self.Max = max(Left+Right+root.val,self.Max)

            return max(Left,Right)+root.val
        dfs(root)
        return self.Max
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

666.路径总和4
对于一棵深度小于 5 的树,可以用一组三位十进制整数来表示。

对于每个整数:

百位上的数字表示这个节点的深度 D,1 <= D <= 4。
十位上的数字表示这个节点在当前层所在的位置 P, 1 <= P <= 8。位置编号与一棵满二叉树的位置编号相同。
个位上的数字表示这个节点的权值 V,0 <= V <= 9。
给定一个包含三位整数的升序数组,表示一棵深度小于 5 的二叉树,
请你返回从根到所有叶子结点的路径之和。

二叉树的数组储存:
1)根节点存储在data[0]
2)左子节点存储在data[2i+1]
3)右子节点存储在data[2
i+2]

在这里插入图片描述
每一个元素存储的位置:
2^(百位数-1)-1+十位数-1 的位置放个位数

先构建二叉树:

nums = [111,221,335,469]
ans = 0
def calculate(nums):
    tree = [None] *15
    for num in nums:
         bai = num//100
         shi = num%100//10
         ge = num%10
         index = ((2**(bai-1))-1)+shi-1
         tree[index] = ge
#
    def dfs(tree, i, currPathSum):
         global ans
         if not tree[i]:
             return
         currPathSum += tree[i]
         if (i >= 7 or (tree[2*i+1]== None and tree[2*i+2]== None)):
                ans += currPathSum
                return
         dfs(tree,2*i+1,currPathSum)
         dfs(tree,2*i+2,currPathSum)
#
    dfs(tree,0,0)
    return ans
calculate(nums)
print(ans)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

226.翻转二叉树
在这里插入图片描述

该例子证明了,遍历之后会返回到最初的节点4.

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:return

        root.left,root.right = root.right,root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

617.合并二叉树
在这里插入图片描述

这道题在上述题的基础上证实了,每一个节点在结束完这一节点的前序遍历后,都会执行两个递归函数之后的操作。

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        root = TreeNode(0)
        if not root1 and not root2:
            return
        elif not root1 and root2:
            return root2
        elif not root2 and root1:
            return root1
        else:
            root.val = root1.val+root2.val
        
        root.left = self.mergeTrees(root1.left,root2.left)
        root.right = self.mergeTrees(root1.right,root2.right)

        return root

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

105.从前序与中序遍历序列构造二叉树
在这里插入图片描述

迭代解法:
首先,前序数组中的第一个元素为二叉树的根节点,记为root,返回时返回root。

从第二个元素开始遍历前序数组,如果该元素在中序遍历中的序号小于栈顶元素的序号,则为左子节点,并将该元素压入栈中。

如果该元素在中序遍历中的序号大于栈顶元素的序号,找出栈顶元素不等于中序遍历(从头往后开始遍历)当前元素的值,是为该元素的右节点。

结束时返回root

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        stack = []
        root = TreeNode(preorder[0])
        stack.append(root)
        index_id = 0

        for i in range(1,len(preorder)):
            child = TreeNode(preorder[i])
            parent = stack[-1]
            if inorder.index(preorder[i]) < inorder.index(stack[-1].val):
                parent.left = child
                stack.append(child)
                
            else:
                while stack and (stack[-1].val == inorder[index_id]):
                    parent = stack.pop()
                    index_id = index_id+1
                child = TreeNode(preorder[i])
                parent.right = child
                stack.append(child)
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

递归解法:
前序遍历中第一个元素为根节点,
中序遍历中从左到第一个根节点的元素为它的左节点
中序遍历中从根节点到最右的元素为它的右节点

前序遍历中第二个元素为左子树的根节点。
由此构成递归结构

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None
        root = TreeNode(preorder[0])
        idx = inorder.index(root.val)

        root.left = self.buildTree(preorder[1:idx+1],inorder[0:idx])
        root.right = self.buildTree(preorder[idx+1:],inorder[idx+1:])
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

105.从中序与后序遍历序列构成二叉树

后序遍历中的最后一个数为根节点,据此实现递归。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return
        root = TreeNode(postorder[-1])
        index_id = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[0:index_id],postorder[0:index_id])
        root.right = self.buildTree(inorder[index_id+1:],postorder[index_id:-1])
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

105.填充每个节点的下一个右侧节点指针
层序遍历。
在此处深入的了解层序遍历:
在for循环之后才会得到整个一层的tmp(当然也不算新知识,只是之前没注意到)
在这里插入图片描述
在这里插入图片描述

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:return
        
        queue = collections.deque()
        queue.append(root)

        while queue:
            tmp = collections.deque()
            size = len(queue)
            for _ in range(size):
                r = queue.popleft()
                tmp.append(r)

                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            
            while tmp:
                p = tmp.popleft()
                if tmp:
                    p.next = tmp[0]
                else:
                    p.next = None
            
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

解法2:
在这里插入图片描述
cur用于横向移动
left用于在二叉树层间移动
从图可知curr.left.next = curr.right
curr.right.next = curry.next.left

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:return
        
        left = root
        curr = root

        while(left.left != None):
            curr = left

            while(curr != None):
                curr.left.next = curr.right
                if(curr.next != None):
                    curr.right.next = curr.next.left
                curr = curr.next
            
            left = left.left
            
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

701.二叉搜索树
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
在这里插入图片描述
在二叉搜索树中,左子节点的所有值<根节点<右子节点的所有值。

1)插入法(迭代):
设置两个节点root和curr,root用于返回,curr用于和当前的值进行比较。

新输入一个元素,如果它的值小于curr,则应放在curr左边。如果左边没有数,直接加入到curr左边,如果左边有数,继续和它判断。
如果它的值大于curr,则应放在curr右边。如果右边没有数,直接加入curr右边,如果右边有数,继续和它判断。

#         self.right = right
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)

        curr = root
        
        while curr:
            if not curr.left and val<curr.val:
                curr.left = TreeNode(val)
                return root
            if not curr.right and val>curr.val:
                curr.right = TreeNode(val)
                return root

            if val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

2)递归法

使用递归时应当时刻注意应该是用return还是赋值。
这里的使用赋值,是因为要求当root.val>val时,要进入的是左子树,而不是返回左子树。

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        
        if not root: 
            node = TreeNode(val)
            return node

        if root.val > val:
            root.left =  self.insertIntoBST(root.left,val)
        else:
            root.right =  self.insertIntoBST(root.right,val)
        return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

在这里插入图片描述

从平衡二叉树可知,左右两侧的高度不超过1,因此取数组的中间位置作为根节点。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:return None

        mid = len(nums)//2
        root = TreeNode(nums[mid])

        root.left = self.sortedArrayToBST(nums[0:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

这里不需要用curr作为第二个指针,直接返回root即可。

235.二叉搜索树
在这里插入图片描述

根据二叉搜索树的性质
p.val,q.val<root.val 说明公共父节点在root的左边
p.val,q.val>root.val 说明公共父节点在root的右边
其余的情况可能有:
p.val = root.val
q.val = root.val
p.val<root.val<q.val
就返回root

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:return

        if p.val>q.val:
            p,q = q,p
        
        if root.val < p.val:
            return self.lowestCommonAncestor(root.right,p,q)
        elif root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        else:
            return root
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

98.验证二叉搜索树

利用中序遍历将二叉搜索树添加到一个数组中,判断是否为递增序列,如果不是返回False。这样的做法会使空间复杂度很高。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        res = []

        def dfs(root):
            if not root: return None
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        
        dfs(root)
        for i in range(1,len(res)):
            if  not (res[i-1] < res[i]):
                return False
                break

        return True
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
class Solution(object):
    
    def validBST(self,root,small,large):
        if root==None:
            return True
        if small>=root.val or large<=root.val:
            return False  
        return self.validBST(root.left,small,root.val) and self.validBST(root.right,root.val,large)
        
        
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.validBST(root,float('-inf'),float('inf'))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

501.二叉搜索树中的众数
在这里插入图片描述

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:

        self.count = 0
        self.countsum = 0
        self.prev = None
        self.res = []

        def dfs(root):
            if not root:
                return None

            dfs(root.left)

            if not self.prev:
                self.count = 1
            elif self.prev.val == root.val:
                self.count += 1
            else:
                self.count = 1
            
            self.prev = root

            if self.count == self.countsum:
                self.res.append(root.val)
            if self.count > self.countsum:
                self.res = []
                self.res.append(root.val)
                self.countsum = self.count
            
            dfs(root.right)
            return
        dfs(root)
        return self.res
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

思路:
中序遍历,结果中如果有一个降序对,说明该两个node需交换;若有两个降序对,说明第一对的前一个node和第二对的后一个node需要交换。

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.x = None
        self.y = None
        self.prev = None
        def dfs(root):
            if not root:return

            dfs(root.left)
            if not self.prev:
                self.prev = root
            else:
                if self.prev.val > root.val:
                    self.y = root
                    if not self.x:
                        self.x = self.prev

            self.prev = root
            dfs(root.right)
        
        dfs(root)
        if self.x and self.y:
            self.x.val,self.y.val = self.y.val,self.x.val
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

思路:
二叉搜索树中序遍历是一个从小到大的序列,但要是先遍历右子树,后遍历左子树,就会得到一个从大到小的序列。
设置一个变量currsum,将每个节点的值加入到currsum中,再赋值给新的节点。

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.currSum = 0

        def dfs(root):
            if not root:
                return

            dfs(root.right)
            

            self.currSum += root.val
            root.val = self.currSum

            dfs(root.left)

        dfs(root)
        return root
            
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/656008
推荐阅读
相关标签
  

闽ICP备14008679号