关于深度优先搜索和广度优先搜索
按照难度递增顺序
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution (object) :
def isSameTree (self, p, q) :
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p == None and q == None :
return True
if p == None or q == None :
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right,q.right)
注意python的null和none的使用
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.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function (p, q )
if (!p && !q){
return true ;
}
if (!p || !q){
return false ;
}
if (p.val !== q.val){
return false ;
}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
};
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
3
4
5
6
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
Note:
题意：判断是不是对称树
Tree & Depth-first Search Breadth-first Search
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 isSymmetric (self, root) :
"""
:type root: TreeNode
:rtype: bool
"""
if root == None :
return True
return self.Helper(root.left, root.right)
def Helper (self, l, r) :
if l == None and r == None :
return True
if l and r and l.val == r.val:
return self.Helper(l.left, r.right) and self.Helper(l.right, r.left)
return False
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.
求二叉树的最大深度
Tree Depth-first Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution (object) :
def maxDepth (self, root) :
"""
:type root: TreeNode
:rtype: int
"""
if root == None :
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
求二叉树的最小深度：根节点到最近叶子节点的路径长度。
同样采用递归的思想：
当根节点为空，返回 0；
当根节点为唯一的二叉树节点时，返回 1；
否则，求解并返回 最小 (非空，保证最终到达叶节点) 左右子树深度 + 1；
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
class Solution (object) :
def minDepth (self, root) :
"""
:type root: TreeNode
:rtype: int
"""
if root == None :
return 0
left, right = 0 , 0
if root.left != None :
left = self.minDepth(root.left)
else :
return self.minDepth(root.right) + 1
if root.right != None :
right = self.minDepth(root.right)
else :
return left + 1
return min(left,right) + 1
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:
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
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)
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
For example:
1
2
3
4
5
6
7
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
1
2
3
4
[
[5,4,11,2],
[5,8,4,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
# 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)
Total Accepted: 93328
For example, given the following binary tree:
All root-to-leaf paths are:
[“1->2->5”, “1->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
class Solution (object) :
def binaryTreePaths (self, root) :
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if root == None :
return res
self.Helper(root, str(root.val), res)
return res
def Helper (self, node, path, res) :
if node == None :
return
if node.left == None and node.right == None :
res.append(path)
return
if node.left:
self.Helper(node.left, path + '->' + str(node.left.val), res)
if node.right:
self.Helper(node.right, path + '->' + str(node.right.val), res)
思路：
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 sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = (len(nums))//2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[0:mid])
root.right = self.sortedArrayToBST(nums[mid + 1: len(nums)])
return root
判断是否为二叉平衡树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution (object) :
def isBalanced (self, root) :
"""
:type root: TreeNode
:rtype: bool
"""
if root == None :
return True
if root.left == None and root.right == None :
return True
if abs(self.depth(root.left) - self.depth(root.right)) > 1 :
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
def depth (self, node) :
if node == None :
return 0
return max(self.depth(node.left), self.depth(node.right)) + 1
medium
Example 1:
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
1
2
3
4
5
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.
大概意思应该是只能抢隔层上的节点，求最大的
这道题前面的两道题都是动归，其中第二题是环形动归，环形动归的解决方案是求两边，然后取一个更大的。
说回这道题，是深搜。
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 rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = 0
if root is None:
return res
rob, not_rob = self.visit(root)
return max(rob, not_rob)
def visit(self, node):
if node is None:
return 0,0
left_rob, left_not_rob = self.visit(node.left)
right_rob, right_not_rob = self.visit(node.right)
rob = node.val + left_not_rob + right_not_rob
not_rob = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
return rob, not_rob
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.
判断 是不是 二叉搜索树
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
# 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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
if root.left:
tmp = root.left
while tmp.right:
tmp = tmp.right
if tmp.val >= root.val:
return False
if root.right:
tmp = root.right
while tmp.left:
tmp = tmp.left
if tmp.val <= root.val:
return False
return self.isValidBST(root.left) and self.isValidBST(root.right)
Preorder 前序
先序遍历的从左数第一个为整棵树的根节点。
中序遍历中根节点是左子树右子树的分割点。
通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。
因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。
递归的建立好左子树和右子树。
(这跟深搜好像没啥关系，纯递归)
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 buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
中序遍历中根节点是左子树右子树的分割点。
后续遍历的最后一个节点为根节点。
同样根据中序遍历找到根节点的位置，然后顺势计算出左子树串的长度。在后序遍历中分割出左子树串和右子树串，递归的建立左子树和右子树。
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 buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not inorder or not postorder:
return None
root = TreeNode(postorder.pop())
ind = inorder.index(root.val)
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root