Tree problem in Leetcode

Posted on | Post modified

二叉树逐层打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Node:
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def printNode(root):
    output=[]
    queue=[root]
    current=[]
    while queue and root:
        nextQueue=[]
        current=[]
        for i in queue:
            current.append(i.val)
            if i.left:
                nextQueue.append(i.left)
            if i.right:
                nextQueue.append(i.right)         
        queue=nextQueue
        output.append(current)

    return output
1
2
3
4
a=Node(1,Node(2),Node(3))
a.left
a.right
a.val
1

1
printNode(a)
[[1], [2, 3]]

二叉树前序遍历（非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def print_node(root):
    stack=[root]
    while stack and root:       
        while root:
            print(root.val)
            if root.left:
                stack.append(root.left)
            root=root.left
        while stack:
            a=stack.pop()
            if a.right:
                root=a.right
                stack.append(root)
                break
a=Node(1,Node(2,Node(4),Node(5)),Node(3,Node(6),Node(7)))
print_node(a)
1
2
4
5
3
6
7

二叉树中序遍历 （非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def print_node(root):
    stack=[root]
    while stack and root:
        while root:
            if root.left:
                stack.append(root.left)
            root=root.left
        while stack:
            a=stack.pop()
            print(a.val)
            if a.right:
                root=a.right
                stack.append(root)
                break

a=Node(1,Node(2,Node(4),Node(5)),Node(3,Node(6),Node(7)))

print_node(a)
4
2
5
1
6
3
7

二叉树后序遍历 （非递归）

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
def print_node(root):
    stack = [root]
    while stack and root:
        while root:
            if root and root not in stack:
                stack.append(root)
            root = root.left
        root = stack[-1]
        while not root.right and stack:
            print(stack.pop().val)
            if stack:
                root = stack[-1]
        if stack:
            root =root.right
            stack[-1].right = None


class Node:
    def __init__(self,val,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
a=Node(1,Node(2,Node(4),Node(5)),Node(3,Node(6),Node(7)))

print_node(a)
4
5
2
6
7
3
1

110. balance binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def check(root):
    if not root:
        return 0
    left=check(root.left)
    right=check(root.right)
    if left==-1 or right==-1 or abs(left-right)>1:
        return -1
    else:
        return max(left,right)+1
def main(root):
    if check(root)!=-1:
        return True
    else:
        return False
a=Node(1,Node(2,Node(3,Node(4))),Node(3))
main(a)
False

100. same tree

1
2
3
4
5
6
7
8
9
10
11
12
def same_tree(p,q):
    if not p and not q:
        return True
    if p.val==q.val and same_tree(p.left,q.left) and same_tree(p.right,q.right):
        return True
    else:
        return False
a=Node(1,Node(2,Node(3,Node(4))),Node(3))
b=Node(1,Node(2,Node(3,Node(4))),Node(4))
print(same_tree(a,b))
b=Node(1,Node(2,Node(3,Node(4))),Node(3))
print(same_tree(a,b))
False
True

101. symmetric tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def symmetric_tree(root):
    def check_symmetric(p,q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val==q.val and check_symmetric(p.left,q.right) and check_symmetric(p.right,q.left):
            return True
        else:
            return False
    if root:
        return check_symmetric(root.left,root.right)
    return False

a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(3)))
print(symmetric_tree(a))
a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(4)))
print(symmetric_tree(a))
True
False

116. Populating Next Right Pointers in Each Node

1
2
3
4
5
6
7
8
9
10
11
12
13
def populate_next_right_pointer(root):
    if not root:
        return
    if root.left:
        root.left.next=root.right
    if root.right:
        if root.next:
            root.right.next=root.next.left
        else:
            root.right.next=None
    populate_next_right_pointer(root.left)
    populate_next_right_pointer(root.right)
    return root

102. Binary Tree Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_tree_level_order_traversal(root):
    if not root:
        return None
    stack=[root]
    res=[]
    while stack:
        newStack=[]
        tmp=[]
        for i in stack:
            tmp.append(i.val)
            if i.left:
                newStack.append(i.left)
            if i.right:
                newStack.append(i.right)
        stack=newStack
        res.append(tmp)
    return res
a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(3)))
print(binary_tree_level_order_traversal(a))
[[1], [2, 2], [3, 4, 4, 3]]

107. Binary Tree Level Order Traversal II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_tree_level_order_traversal(root):
    if not root:
        return None
    stack=[root]
    res=[]
    while stack:
        newStack=[]
        tmp=[]
        for i in stack:
            tmp.append(i.val)
            if i.left:
                newStack.append(i.left)
            if i.right:
                newStack.append(i.right)
        stack=newStack
        res.append(tmp)
    return res[::-1]
a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(3)))
print(binary_tree_level_order_traversal(a))
[[3, 4, 4, 3], [2, 2], [1]]

103. Binary Tree Zigzag Level Order Traversal

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
def binary_tree_level_order_traversal(root):
    if not root:
        return None
    stack=[root]
    res=[]
    while stack:
        newStack=[]
        tmp=[]
        for i in stack:
            tmp.append(i.val)
            if i.left:
                newStack.append(i.left)
            if i.right:
                newStack.append(i.right)
        stack=newStack
        res.append(tmp)
    newRes=[]
    flag=True
    while res:
        if flag:
            newRes.append(res.pop(0))
            flag=False
        else:
            newRes.append(res.pop(0)[::-1])
            flag=True
    return newRes
a=Node(3,Node(9),Node(20,Node(15),Node(7)))
print(binary_tree_level_order_traversal(a))
[[3], [20, 9], [15, 7]]

637. Average of Levels in Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binary_tree_level_order_traversal(root):
    if not root:
        return None
    stack=[root]
    res=[]
    while stack:
        newStack=[]
        tmp=[]
        for i in stack:
            tmp.append(i.val)
            if i.left:
                newStack.append(i.left)
            if i.right:
                newStack.append(i.right)
        stack=newStack
        res.append(tmp)

    return [sum(x)/len(x) for x in res]
a=Node(3,Node(9),Node(20,Node(15),Node(7)))
print(binary_tree_level_order_traversal(a))
[3.0, 14.5, 11.0]

314. Binary Tree Vertical Order Traversal

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
from collections import defaultdict
class newNode:
    def __init__(self,node,index):
        self.node=node
        self.index=index
def binary_tree_level_order_traversal(root):
    if not root:
        return None
    stack=[newNode(root,0)]
    res=[]
    while stack:
        newStack=[]

        for i in stack:
            res.append((i.index,i.node.val))
            if i.node.left:
                newStack.append(newNode(i.node.left,i.index-1))
            if i.node.right:
                newStack.append(newNode(i.node.right,i.index+1))
        stack=newStack
    newRes=defaultdict(list)

    for i,j in res:
        newRes[i].append(j)
    newRes=sorted(newRes.items(),key=lambda x:x[0])
    res=[]
    for values in newRes:
        res.append(values[1])
    return res

a=Node(3,Node(9),Node(20,Node(15),Node(7)))
print(binary_tree_level_order_traversal(a))
[[9], [3, 15], [20], [7]]

257. Binary Tree Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_tree_paths(root):
    def helper(node,path):
        if not node:
            return None
        if not node.left and not node.right:
            return [path+[node.val]]
        if node.left and node.right:
            left=helper(node.left,path+[node.val])
            right=helper(node.right,path+[node.val])
            return left+right
        if node.left:
            left=helper(node.left,path+[node.val])
            return left
        if node.right:
            right=helper(node.right,path+[node.val])
            return right
    return helper(root,[])
a=Node(3,Node(1),Node(2))
binary_tree_paths(a)
[[3, 1], [3, 2]]

112. Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def path_sum(root,n):
    def helper(node,path):
        if not node:
            return None
        if not node.left and not node.right:
            return [path+[node.val]]
        if node.left and node.right:
            left=helper(node.left,path+[node.val])
            right=helper(node.right,path+[node.val])
            return left+right
        if node.left:
            left=helper(node.left,path+[node.val])
            return left
        if node.right:
            right=helper(node.right,path+[node.val])
            return right
    res=helper(root,[])
    for i in res:
        if sum(i)==n:
            return True
    return False
a=Node(3,Node(1),Node(2))
print(path_sum(a,5))
True

113. Path Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def path_sum(root,n):
    def helper(node,path):
        if not node:
            return None
        if not node.left and not node.right:
            return [path+[node.val]]
        if node.left and node.right:
            left=helper(node.left,path+[node.val])
            right=helper(node.right,path+[node.val])
            return left+right
        if node.left:
            left=helper(node.left,path+[node.val])
            return left
        if node.right:
            right=helper(node.right,path+[node.val])
            return right
    res=helper(root,[])
    newRes=[]
    for i in res:
        if sum(i)==n:
            newRes.append(i)
    return newRes
a=Node(3,Node(1),Node(2))
print(path_sum(a,5))
[[3, 2]]

129. Sum Root to Leaf Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def path_sum(root,n):
    def helper(node,path):
        if not node:
            return None
        if not node.left and not node.right:
            return [path+[node.val]]
        if node.left and node.right:
            left=helper(node.left,path+[node.val])
            right=helper(node.right,path+[node.val])
            return left+right
        if node.left:
            left=helper(node.left,path+[node.val])
            return left
        if node.right:
            right=helper(node.right,path+[node.val])
            return right
    res=helper(root,[])
    newRes=[]
    for i in res:
        i=map(str,i)
        newRes.append(int("".join(i)))
    return sum(newRes)
a=Node(3,Node(1),Node(2))
print(path_sum(a,5))
63

124. Binary Tree Maximum Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_tree_maximum_path_sum(root):
    maxSum=[float('-inf')]
    def helper(root,maxSum):
        if not root:
            return 0
        left=helper(root.left,maxSum)
        right=helper(root.right,maxSum)
        temp=max(root.val,root.val+left,root.val+right)
        maxSum[0]=max(maxSum[0],temp,left+root.val+right)
        return temp
    helper(root,maxSum)
    return maxSum[0]
a=Node(-10,Node(9),Node(20,Node(15),Node(7)))
binary_tree_maximum_path_sum(a)
42

563. Binary Tree Tilt

1
2
3
4
5
6
7
8
9
10
11
12
13
def add(root):
    if not root:
        return 0
    return add(root.left)+root.val+add(root.right)
def tilt(root):
    if not root:
        return 0
    left=tilt(root.left)
    right=tilt(root.right)
    diff=abs(add(root.left)-add(root.right))
    return left+right+diff
a=Node(1,Node(2),Node(3))
tilt(a)

235. Lowest Common Ancestor of a Binary Search Tree

1
2
3
4
5
6
7
8
9
def lowest_common_ancestor(root,p,q):
    if p.val>q.val:
        p,q=q,p
    if p.val<=root.val and q.val>=root.val:
        return root
    if q.val<root.val:
        return lowest_common_ancestor(root.left,p,q)
    if p.val>root.val:
        return lowest_common_ancestor(root.right,p,q)

270. Closest Binary Search Tree Value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def closest_binary_search_tree(root,target):
    r=root.val
    localMinimum=abs(r-target)
    while root:
        if abs(root.val-target)<=localMinimum:
            r=root.val
        else:
            return r
        if target>r:
            root=root.right
        elif target<r:
            root=root.left
        else:
            return r   
    return r
a=Node(1,Node(2),Node(3))
print(closest_binary_search_tree(a,4))
a=Node(1,Node(2),Node(4))
print(closest_binary_search_tree(a,4))
3
4

272. Closest Binary Search Tree Value II

这道题要维持一个k长度的list，所以可以中序遍历，然后不断更新最后添加元素和队列首元素与target的差值

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(object):
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        res = []
        self.helper(root, target, k ,res)
        return res
    def helper(self, root, target, k, res):
        if not root:
            return
        self.helper(root.left, target, k, res)
        if len(res) < k:
            res.append(root.val)
        else:
            if abs(target - root.val) < abs(target - res[0]):
                res.pop(0)
                res.append(root.val)

        self.helper(root.right, target , k , res)
1