LeetCode day20

2020-05-14 3 minutes read

LeetCode

#LeetCode

views 540 words

Diffculty: Medium

98. Validate Binary Search Tree

Topic: Tree, DFS

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Approach1

Recurrsive

def isValidBST(root: TreeNode) -> bool:
    def dfs(node, min_val, max_val):
        if not node:  # 边界条件，如果node为空肯定是二叉搜索树
            return True
        if not min_val < node.val < max_val:  # 如果当前节点超出上下界范围，肯定不是
            return False
        # 走到下面这步说明已经满足了如题所述的二叉搜索树的前两个条件
        # 那么只需要递归判断当前节点的左右子树是否同时是二叉搜索树即可
        return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)

    return dfs(root, float('-inf'), float('inf'))

102. Binary Tree Level Order Traversal

Topic: Tree, BFS

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Approach1

def levelOrder(root: TreeNode) -> List[List[int]]:
    res = []
    queue = [root]
    while queue:
        val = []
        for i in queue:
            if i:
                val.append(i.val)
        if val:
            res.append(val)
        queue = [child for i in queue if i for child in (i.left, i.right)]
    return res

Approach2

my2

def levelOrder(root: TreeNode) -> List[List[int]]:
    
    res = []
    if not root:
        return []
    
    queue = [root]
    while queue:
        tmp = []
        new_q = []
        for node in queue:
            tmp.append(node.val)
            if node.left:
                new_q.append(node.left)
            if node.right:
                new_q.append(node.right)
        res.append(tmp)
        queue = new_q
        
    return res

103. Binary Tree Zigzag Level Order Traversal

Topic: Stack, Tree, BFS

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Approach1

def zigzagLevelOrder(root: TreeNode) -> List[List[int]]:
    if not root: return []
    queue = [root]
    res= []
    level = 1
    while queue:
        tmp = []
        new_q = []
        for node in queue:
            if node:
                tmp.append(node.val)
            if node.left:
                new_q.append(node.left)
            if node.right:
                new_q.append(node.right)    
        if level % 2 == 1:      
            res.append(tmp)
        else:
            tmp.reverse()
            res.append(tmp)
        queue = new_q
        level += 1
    return res

Approach2

105. Construct Binary Tree from Preorder and Inorder Traversal

Topic: Stack, Tree, DFS

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Approach1

def buildTree(preorder: List[int], inorder: List[int]) -> TreeNode:
    # 实际上inorder 和 postorder一定是同时为空的，因此你无论判断哪个都行
    if not preorder:
        return None
    root = TreeNode(preorder[0])

    i = inorder.index(root.val)
    print(i)  # 1 0 1 0 0
    root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
    root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])

    return root

时间复杂度：由于每次递归我们的inorder和preorder的总数都会减1，因此我们要递归N次，故时间复杂度为 O(N)，其中N为节点个数。

空间复杂度：我们使用了递归，也就是借助了额外的栈空间来完成，由于栈的深度为N，因此总的空间复杂度为 O(N)，其中N为节点个数。