leetcode上面的Tree合集_isvalidinterval

94.Binary Tree Inorder Traversal

二叉树的中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        result = []
        result.extend(self.inorderTraversal(root.left))
        result.append(root.val)
        result.extend(self.inorderTraversal(root.right))
        
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

95.Unique Binary Search Trees II

与96题相似，就是将节点数目为n的二叉树打印出来

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n==0:
            return []
        x = self.buildTree([1,n])
        return x
    
    
    def buildTree(self,interval):
        if interval[0] > interval[1]:
            return [None]
        result = []
        for i in range(interval[0],interval[1]+1):
            listLeft = self.buildTree([interval[0],i-1])
            listRight = self.buildTree([i+1,interval[1]])
            for j in range(len(listLeft)):
                for k in range(len(listRight)):
                    x = TreeNode(i)
                    x.left = listLeft[j]
                    x.right = listRight[k]
                    result.append(x) 
        return result      
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

96. Unique Binary Search Trees

计算节点为n的二叉树有几种不同的形状，通过找规律得到。

class Solution:
    def numTrees(self, n: int) -> int:
        numList = [1]
        numList.append(1)
        numList.append(2)
        if n <= 2:
            return numList[n]
        for num in range(3,n+1):
            count = 0
            for i in range(num):
                count  += numList[i] * numList[num-(i+1)]
            numList.append(count)
        return numList[n]
1
2
3
4
5
6
7
8
9
10
11
12
13

98.Validate Binary Search Tree

校验一棵二叉树是否是BSF
就是判断每一个节点是否满足一定的区间条件

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import math
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.isValidInterval(root,[-math.inf,math.inf])
        
    
    
    def isValidInterval(self,root,interval):
        if root == None:
            return True
        intervalLeft = []
        intervalRight = []
        r = True
        if root.val < interval[1] and interval[0] < root.val:
            intervalLeft.append(interval[0])
            intervalLeft.append(root.val)
            intervalRight.append(root.val)
            intervalRight.append(interval[1])
            r = self.isValidInterval(root.left,intervalLeft) and self.isValidInterval(root.right,intervalRight)
        else:
            return False
        return r
        
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

99. Recover Binary Search Tree

一个二叉树中有两个节点错位了，使用了中序遍历和冒泡排序，但是时间复杂度就是O（n^2）

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root==None:
            return root
        #中序遍历
        l = self.inorderTraversal(root)
        #冒泡排序
        for i in range(len(l)-1):
             for j in range(len(l)-1):
                    if l[j].val > l[j+1].val:
                        temp = l[j].val
                        l[j].val = l[j+1].val
                        l[j+1].val = temp
                                                           
    def inorderTraversal(self,root):
        if root==None:
            return []
        result = []
        result.extend(self.inorderTraversal(root.left))
        result.append(root)
        result.extend(self.inorderTraversal(root.right))
        return result   
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

100.SameTree

判断两棵树否是一样的二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == None and q == None:
            return True
        elif (p==None and q) or (p and q==None):
            return False
        if p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

101.Symmetric Tree

判断一棵二叉树是否是对称的

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        return self.symmetric(root.left,root.right)
    
    def symmetric(self,p1,p2):
        if p1 == None and p2 == None:
            return True
        elif p1==None and p2:
            return False
        elif p1 and p2==None:
            return False
        if p1.val == p2.val:
            return self.symmetric(p1.left,p2.right) and self.symmetric(p1.right,p2.left)
        return  False
        
         
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

102. Binary Tree Level Order Traversal

层次遍历，使用队列

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = list()
        queue = []
        if root == None:
            return []
        queue.append([root])
        result.append([root.val])
        for i in queue:
            temp = []
            queue1 = []
            for j in i:
                if j.left:
                    queue1.append(j.left)
                    temp.append(j.left.val)
                    print(j.left.val)
                if j.right:
                    queue1.append(j.right)
                    temp.append(j.right.val)
            if len(temp):
                result.append(temp)
                queue.append(queue1)
                
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

105. Construct Binary Tree from Preorder and Inorder Traversal

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

106. Construct Binary Tree from Inorder and Postorder Traversal

利用中序和后序遍历列表构建二叉树

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