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.
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
elif p is not None and q is not None:
if p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right):
return True
else:
return False
else:
return False
Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
re = []
if not root:
return re
stack.append(root)
while len(stack) > 0:
tmp = stack.pop()
re.append(tmp.val)
if tmp.right:
stack.append(tmp.right)
if tmp.left:
stack.append(tmp.left)
return re
Given a binary tree, return the inorder traversal of its nodes' values.
注意这里对inorder的处理
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
re = []
if not root:
return re
stack.append(root)
while len(stack) > 0:
tmp = stack.pop()
if tmp.right: # 不管其他情况，右节点先放进栈
stack.append(tmp.right)
tmp.right = None # 注意这里置空
if tmp.left: # 本节点和左节点的处理
stack.append(tmp)
stack.append(tmp.left)
tmp.left = None
else:
re.append(tmp.val)
return re
Given a binary tree, return the postorder traversal of its nodes' values.
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
re = []
if not root:
return re
stack.append(root)
while len(stack) > 0:
tmp = stack.pop()
if tmp.left is not None or tmp.right is not None:
stack.append(tmp)
if tmp.right:
stack.append(tmp.right)
tmp.right = None
if tmp.left:
stack.append(tmp.left)
tmp.left = None
else:
re.append(tmp.val)
return re
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
class Solution(object):
def cal(self, node, prevSum):
if not node:
return 0
if not node.left and not node.right:
return prevSum*10 + node.val
return self.cal(node.left, prevSum*10 + node.val) + self.cal(node.right, prevSum*10 + node.val)
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.cal(root, 0)
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,
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.
注意这里怎样设置全局变量
class Solution(object):
def __init__(self):
self.target = 0
def isLeaf(self, node):
if node.left or node.right:
return False
else:
return True
def cal(self, node, prevSum):
if not node:
return False
if self.isLeaf(node):
return prevSum + node.val == self.target
else:
return self.cal(node.left, prevSum + node.val) or self.cal(node.right, prevSum + node.val)
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
self.target = sum
return self.cal(root, 0)
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,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
class Solution(object):
def pathSum(self, root, sum1):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if root==None:
return []
stack,res=[(root,[root.val])],[]
while stack:
temp,val=stack.pop()
if not temp.left and not temp.right:
if sum(val)==sum1:
res.append(val)
if temp.left:
stack.append((temp.left,val+[temp.left.val]))
if temp.right:
stack.append((temp.right,val+[temp.right.val]))
return res
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.
class Solution(object):
def __init__(self):
self.mDepth = 0
def isLeaf(self, node):
if not node.left and not node.right:
return True
return False
def depth(self, node, prevDepth):
if self.isLeaf(node) and prevDepth + 1 > self.mDepth:
self.mDepth = prevDepth + 1
return
if node.left:
self.depth(node.left, prevDepth + 1)
if node.right:
self.depth(node.right, prevDepth + 1)
return
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.depth(root, 0)
return self.mDepth
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]
]
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
tmp = []
stack = []
re = []
line = []
stack.append(root)
toggle = -1
while stack or tmp:
while len(stack) > 0:
t = stack.pop()
line.append(t.val)
if toggle == -1:
if t.left:
tmp.append(t.left)
if t.right:
tmp.append(t.right)
else:
if t.right:
tmp.append(t.right)
if t.left:
tmp.append(t.left)
toggle = -1 * toggle
stack = tmp
tmp = []
re.append(line)
line = []
return re
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
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root: return True
stack = []
stack.append((root.left, root.right))
while stack:
l, r = stack.pop()
if r and l:
if not l.val == r.val:
return False
else:
stack.append((l.left, r.right))
stack.append((l.right, r.left))
else:
if not l and not r:
pass
else:
return False
return True
class Solution(object):
def checkSym(self, n1, n2):
if not n1 and not n2:
return True
if n1 and n2 and n1.val == n2.val:
return self.checkSym(n1.left,n2.right) and self.checkSym(n1.right, n2.left)
return False
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root: return True
return self.checkSym(root.left, root.right)
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example: Given the below binary tree,
1
/ \
2 3
Return 6.
这里用path来计算这个节点往下的最大值分支。值得学习的思路。在计算完左右分支的最大值之后，更新总体最大值，同时给上一级返回最大值分支。
class Solution(object):
def __init__(self):
self.maxLength = -9999
def path(self, node):
if not node:
return 0
leftPath = max(self.path(node.left),0)
rightPath = max(self.path(node.right),0)
self.maxLength = max(leftPath + rightPath + node.val, self.maxLength)
return max(leftPath, rightPath) + node.val
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.path(root)
return self.maxLength
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.
class Solution(object):
def depth(self, node):
if node is None:
return True, 0
if node.left is None and node.right is None:
return True, 1
re1, val1 = self.depth(node.left)
re2, val2 = self.depth(node.right)
if re1 and re2 and abs(val1 - val2) < 2:
return True, max(val1, val2)+1
return False, max(val1, val2)+1
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None: return True
re1, val1 = self.depth(root.left)
re2, val2 = self.depth(root.right)
if re1 and re2 and abs(val1 - val2) < 2:
return True
return False
Given a binary tree, flatten it to a linked list in-place.
For example, Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
这里对递归处理得非常好。
class Solution(object):
def flatten(self, root):
self.flattenTree(root)
def flattenTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if not root: return None, None
leftHead, leftTail = self.flattenTree(root.left)
rightHead, rightTail = self.flattenTree(root.right)
if not leftHead and not rightHead:
return root, root
elif leftHead and not rightHead:
root.left = None
root.right = leftHead
return root, leftTail
elif not leftHead and rightHead:
return root, rightTail
else:
root.right = leftHead
root.left = None
leftTail.right = rightHead
return root, rightTail
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space. For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
class Solution:
# @param root, a tree link node
# @return nothing
def connect(self, root):
if not root: return
stack = []
stack.append(root)
while stack:
cur = []
nextLine = []
while stack:
tmp = stack[0]
stack = stack[1:]
if tmp.left:
nextLine.append(tmp.left)
if tmp.right:
nextLine.append(tmp.right)
cur.append(tmp)
for i in range(len(cur)):
if i != len(cur)-1:
cur[i].next = cur[i+1]
else:
cur[i].next = None
stack = nextLine
cur = nextLine = []
return