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[2i+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