【leetcode】树 Tree

发表于 更新于
树的练习题（简单）

1、leetcode100：相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def isSameTree(p, q):
    # 先判断是否全为空，是则返回；再判断是否有一个为空，是则返回，再判断两个值是否相等
    if not p and not q:
        return True
    elif p == None or q == None:
        return False
    elif p.root != q.root:
        return False
    return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

t1 = getBTreewithBFS([1,3,2])
t2 = getBTreewithBFS([1,3,2])
print(isSameTree(t1, t2))

2、leetcode101：对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def isSymmetric(root):
    if not root: return True
    def match(l, r):
        if not l and not r: return True
        if not l or not r: return False
        return l.root == r.root and match(l.left, r.right) and match(l.right, r.left)
    return match(root.left , root.right)

t1 = getBTreewithBFS([1,2,2,3,4,4,3])
t2 = getBTreewithBFS([1,3,2])
print(isSymmetric(t1))
print(isSymmetric(t2))

3、leetcode226：翻转二叉树

翻转一棵二叉树。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def invertTree(root):
    if root != None:
        node = root
        node.left, node.right = invertTree(node.right), invertTree(node.left)
    else:
        return None
    return node

BT1 = Bnode(4, Bnode(2, Bnode(1), Bnode(3)), Bnode(7, Bnode(6), Bnode(9)))
BT2 = getBTreewithBFS([4,2,7,1,3,6,9])
print(PrintBTree(invertTree(BT1)))
print(PrintBTree(invertTree(BT2)))

4、leetcode104：二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]
返回它的最大深度 3 

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def maxDepth(root):
    if root is None: 
        return 0 
    else: 
        left_height = maxDepth(root.left) 
        right_height = maxDepth(root.right) 
        return max(left_height, right_height) + 1

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(maxDepth(BT))

5、leetcode111：二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def minDepth(root):
    if not root: return 0
    if not root.left: return minDepth(root.right) + 1
    if not root.right: return minDepth(root.left) + 1
    return min(minDepth(root.left), minDepth(root.right)) + 1

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(minDepth(BT))

6、leetcode111：平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def depth(root):
    if not root:
        return 0
    return max(depth(root.left), depth(root.right)) + 1
        
def isBalanced(root):
    if not root:
        return True
    if not isBalanced(root.left) or not isBalanced(root.right):
        return False
    depth_left, depth_right = depth(root.left), depth(root.right)
    if abs(depth_left - depth_right) < 2:
        return True
    else:
        return False

BT = getBTreewithBFS([3,9,20,None,None,15,7])
print(isBalanced(BT))

7、leetcode108：将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def sortedArrayToBST(nums):
    if not nums:
        return
    mid = len(nums)//2
    root = Bnode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root

BT = sortedArrayToBST([-10,-3,0,5,9])
print(PrintBTree(BT))

8、leetcode617：合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Bnode:
    '''二叉树的节点'''
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.left = left
        self.right = right

def getBTreewithBFS(l):
    '''给定二叉树的层序遍历, 重建该二叉树'''
    if l[0]:
        root = Bnode(l[0])
        nodes = [root]
        id = 1
        while nodes and id < len(l):
            node = nodes[0] # 依次为每个节点分配子节点
            node.left = Bnode(l[id]) if l[id] else None
            nodes.append(node.left)
            node.right = Bnode(l[id+1]) if id<len(l)-1 and l[id+1] else None
            nodes.append(node.right)
            id+=2 # 每次取出两个节点
            nodes.pop(0)
        return root
    else:
        return None

def PrintBTree(root):
    '''打印二叉树, 从顶到底'''
    tmp = []
    result = []
    if root == None:
        return result
    tmp.append(root)
    while tmp:
        newNode = tmp.pop(0)
        if newNode == None:
            result.append(None)
        else:
            result.append(newNode.root)
            if newNode.left or newNode.right:
                tmp.append(newNode.left)
                tmp.append(newNode.right)
    return result

#################################################################

def mergeTrees(t1, t2):
    if not t1 and t2:
        return t2
    elif t1 and t2:
        t1.root = t2.root+t1.root
        t1.left = mergeTrees(t1.left, t2.left)
        t1.right = mergeTrees(t1.right, t2.right)
    return t1

t1 = getBTreewithBFS([1,3,2,5])
t2 = getBTreewithBFS([2,1,3,None,4,None,7])
BT = mergeTrees(t1, t2)
print(PrintBTree(BT))