题目序号 110、107、104、101、100、684、666

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7
Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Return false.

def isBalanced(self, root):
    flag = []
    self.helper(root, flag)
    return flag == []

def helper(self, root, flag):
    if not root:
        return 0
    leftHeight = self.helper(root.left, flag)
    rightHeight = self.helper(root.right, flag)
    if abs(leftHeight - rightHeight) > 1:
        flag.append(False)
    return max(leftHeight, rightHeight) + 1

# BFS
def isBalanced(self, root):
    queue = []
    queue.append(root)
    while queue:
        curr = queue.pop(0)
        if curr:
            if abs(self.height(curr.left) - self.height(curr.right)) > 1:
                return False
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
    return True

# DFS
def isBalanced(self, root):
    stack = []
    stack.append(root)
    while stack:
        curr = stack.pop()
        if curr:
            if abs(self.height(curr.left) - self.height(curr.right)) > 1:
                return False
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)
    return True

def height(self, root):
    if not root:
        return 0
    return max(self.height(root.left), self.height(root.right)) + 1

107. Binary Tree Level Order Traversal II

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

For example:

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

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

# dfs recursively
def levelOrderBottom1(self, root):
    res = []
    self.dfs(root, 0, res)
    return res

def dfs(self, root, level, res):
    if root:
        if len(res) < level + 1:
            res.insert(0, [])
        res[-(level+1)].append(root.val)
        self.dfs(root.left, level+1, res)
        self.dfs(root.right, level+1, res)

# dfs + stack
def levelOrderBottom2(self, root):
    stack = [(root, 0)]
    res = []
    while stack:
        node, level = stack.pop()
        if node:
            if len(res) < level+1:
                res.insert(0, [])
            res[-(level+1)].append(node.val)
            stack.append((node.right, level+1))
            stack.append((node.left, level+1))
    return res

# bfs + queue
def levelOrderBottom(self, root):
    queue, res = collections.deque([(root, 0)]), []
    while queue:
        node, level = queue.popleft()
        if node:
            if len(res) < level+1:
                res.insert(0, [])
            res[-(level+1)].append(node.val)
            queue.append((node.left, level+1))
            queue.append((node.right, level+1))
    return res

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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


# BFS + deque
def maxDepth(self, root):
    if not root:
        return 0
    from collections import deque
    queue = deque([(root, 1)])
    while queue:
        curr, val = queue.popleft()
        if not curr.left and not curr.right and not queue:
            return val
        if curr.left:
            queue.append((curr.left, val+1))
        if curr.right:
            queue.append((curr.right, val+1))

# Recursively
def maxDepth1(self, root):
    if not root:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

# DFS
def maxDepth(self, root):
    res = 0
    stack = [(root, 0)]
    while stack:
        node, level = stack.pop()
        if not node:
            res = max(res, level)
        else:
            stack.append((node.right, level+1))
            stack.append((node.left, level+1))
    return res

# BFS + deque
def maxDepth(self, root):
    if not root:
        return 0
    from collections import deque
    queue = deque([(root, 1)])
    while queue:
        curr, val = queue.popleft()
        if not curr.left and not curr.right and not queue:
            return val
        if curr.left:
            queue.append((curr.left, val+1))
        if curr.right:
            queue.append((curr.right, val+1))


# Recursively
def maxDepth1(self, root):
    if not root:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

# DFS
def maxDepth(self, root):
    res = 0
    stack = [(root, 0)]
    while stack:
        node, level = stack.pop()
        if not node:
            res = max(res, level)
        else:
            stack.append((node.right, level+1))
            stack.append((node.left, level+1))
    return res

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

  1
 / \
2   2
 \   \
 3    3

Note: Bonus points if you could solve it both recursively and iteratively.

def isSymmetric(self, root):
    if not root:
        return True
    queue = []
    queue.append((root.left, root.right))
    while queue:
        l, r = queue.pop(0)
        if not l and not r:
            continue
        if not l or not r:
            return False
        if l.val != r.val:
            return False
        queue.append((l.left, r.right))
        queue.append((l.right, r.left))
    return True

def isSymmetric(self, root):
    if not root:
        return True
    return self.dfs(root.left, root.right)

def dfs(self, l, r):
    if l and r:
        return l.val == r.val and self.dfs(l.left, r.right) and self.dfs(l.right, r.left)
    return l == r

An iterative version:

def isSymmetric(self, root):
    if not root:
        return True
    stack = [(root.left, root.right)]
    while stack:
        l, r = stack.pop()
        if not l and not r:
            continue
        if not l or not r:
            return False
        if l.val != r.val:
            return False
        stack.append((l.left, r.right))
        stack.append((l.right, r.left))
    return True

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两棵树是否全等

Good answer, it seems you can shorten your code as:

def isSameTree(self, p, q):
    if p and q:
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
    else:
        return p == q



def isSameTree1(self, p, q):
    if p and q:
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
    else:
        return p == q

# DFS with stack
def isSameTree2(self, p, q):
    stack = [(p, q)]
    while stack:
        node1, node2 = stack.pop()
        if not node1 and not node2:
            continue
        elif None in [node1, node2]:
            return False
        else:
            if node1.val != node2.val:
                return False
            stack.append((node1.right, node2.right))
            stack.append((node1.left, node2.left))
    return True

# BFS with queue
def isSameTree3(self, p, q):
    queue = [(p, q)]
    while queue:
        node1, node2 = queue.pop(0)
        if not node1 and not node2:
            continue
        elif None in [node1, node2]:
            return False
        else:
            if node1.val != node2.val:
                return False
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
    return True


# dfs + stack
def isSameTree(self, p, q):
    stack = [(p, q)]
    while stack:
        n1, n2 = stack.pop()
        if n1 and n2 and n1.val == n2.val:
            stack.append((n1.right, n2.right))
            stack.append((n1.left, n2.left))
        elif not n1 and not n2:
            continue
        else:
            return False
    return True

684. Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this:

1

/

2 - 3

Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2

|

4 - 3

Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

666. Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

The hundreds digit represents the depth D of this node, 1 <= D <= 4. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree. The units digit represents the value V of this node, 0 <= V <= 9. Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221] Output: 12 Explanation: The tree that the list represents is:

3

/

5 1

The path sum is (3 + 5) + (3 + 1) = 12. Example 2:

Input: [113, 221] Output: 4 Explanation: The tree that the list represents is:

3

1

The path sum is (3 + 1) = 4. 题目大意： 给定深度不超过5的二叉树，用三位数xyz表示节点（x表示深度，y表示在某层的位置，z表示节点的值）。

求从根节点到每一个叶子节点的路径之和

解题思路： 假设某节点前两位数为xy，则其父亲节点前两位数为(x - 1) * 10 + (y + 1) / 2