leetcode第五部分

关于二叉树
tag:tree

二叉树的遍历

中序遍历

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

1
2
3
4
5
1
 \
  2
 /
3

return [1,3,2].

递归recursively

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if root == None:
            return res
        self.helper(root, res)
        return res
        
    def helper(self, root, res):
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

迭代iteratively 

1
2
3
4
5
6
7
8
9
10
11
def inorderTraversal(self, root):
    res, stack = [], []
    while True:
        while root:
            stack.append(root)
            root = root.left
        if not stack:
            return res
        node = stack.pop()
        res.append(node.val)
        root = node.right

前序遍历 根左右

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return [1,2,3].

1
2
3
4
5
6
7
8
9
10
def preorderTraversal(self, root):
    ret = []
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            ret.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    return ret

层序遍历

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],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        ans, level = [], [root]
        while level:
            ans.append([node.val for node in level])
            temp = []
            for node in level:
                temp.extend([node.left, node.right])
            print temp
            level = [leaf for leaf in temp if leaf]
        return ans

Path Sum系列

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None:
            return False
        if root.val == sum and root.left == None and root.right == None:
            return True
        sum = sum - root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return
[
[5,4,11,2],
[5,8,4,5]
]

tag: dfs 

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        res = []
        if root == None:
            return res
        self.helper(root, sum, [], res)
        return res
        
    def helper(self, root, sum, path, res):
        if root.val == sum and root.left == None and root.right == None:
            path.append(root.val)
            res.append(path)
        if root.left:
            self.helper(root.left, sum - root.val, path+[root.val], res)
        if root.right:
            self.helper(root.right, sum - root.val, path+[root.val], res)

437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

1
2
3
4
5
6
7
8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

这道题让我们求二叉树的路径的和等于一个给定值，说明了这条路径不必要从根节点开始，可以是中间的任意一段，而且二叉树的节点值也是有正有负。

利用前序遍历，对于每个遍历到的节点进行处理，维护一个变量pre记录之前的路径和，然后用cur为pre加上当前节点值，如果cur等于sum，那么返回结果时要加一，然后对当前节点的左右节点调用递归函数求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        return self.helper(root, 0, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
        
    def helper(self, node, pre, sum):
        if not node:
            return 0
        cur = pre + node.val
        return (cur == sum) + self.helper(node.left, cur, sum) + self.helper(node.right, cur, sum)

卡特兰数

96. Unique Binary Search Trees

这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下：

这是 卡特兰数 的一种定义方式，是一个典型的动态规划的定义方式（根据其实条件和递推式求解结果）。所以思路也很明确了，维护量 res[i] 表示含有 i 个结点的二叉查找树的数量。根据上述递推式依次求出 1 到 n 的的结果即可。

时间上每次求解 i 个结点的二叉查找树数量的需要一个 i 步的循环，总体要求 n 次，所以总时间复杂度是 O(1+2+…+n)=O(n^2)。空间上需要一个数组来维护，并且需要前 i 个的所有信息，所以是 O(n)。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        res = [0] * (n+1)
        res[0] = 1
        res[1] = 1
        for i in range(2, n+1):
            for j in range(i):
                res[i] += res[j] * res[i - j - 1]
        return res[n]

卡特兰数——维基百科

随便举个栗子：

C8取4除以5 = 8 7 6 5 / 5 4 3 2 * 1 = 14

下面这道题不是卡特兰数

95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5
6
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        return self.helper(1, n + 1)
        
    def helper(self, start, end):
        res = []
        if start == end:
            return None
        for tmp in range(start, end):
            left = self.helper(start, tmp)
            right = self.helper(tmp + 1, end)
            for i in left or [None]:
                for j in right or [None]:
                    node = TreeNode(tmp)
                    node.left = i
                    node.right = j
                    res.append(node)
        return res
算法
算法