打卡Day15
- 1.222.完全二叉树的节点个数
- 2.110.平衡二叉树
- 3.257. 二叉树的所有路径
- 4.404. 左叶子之和
- 5.可变和不可变类型区分
1.222.完全二叉树的节点个数
题目链接：222.完全二叉树的节点个数
文档讲解： 代码随想录
（1）针对普通二叉树
class Solution(object):
def __init__(self):
self.count = 0
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
def dfs(node):
if not node:
return
self.count += 1
dfs(node.left)
dfs(node.right)
dfs(root)
return self.count
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
#后序递归遍历
return self.getSum(root)
def getSum(self, node):
if not node:
return 0
leftNum = self.getSum(node.left)
rightNum = self.getSum(node.right)
summ = leftNum + rightNum + 1
return summ
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
#迭代法
if not root:
return 0
queue = collections.deque([root])
count = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return count
（2）题目中说了是完全二叉树，可以减少时间复杂度
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left = root.left
right = root.right
leftDepth = 0
rightDepth = 0
while left:
left = left.left
leftDepth += 1
while right:
right = right.right
rightDepth += 1
if leftDepth == rightDepth:
return (2 << leftDepth) - 1 #注意(2<<1) 相当于2^2，所以leftDepth初始为0
return self.countNodes(root.left) + self.countNodes(root.right) + 1
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
count = 1 #count = 0
left = root.left
right = root.right
while left and right:
count += 1
left = left.left
right = right.right
if not left and not right:
#同时到底说明是满二叉树
return 2 ** count - 1 #return (2 << count) - 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1
2.110.平衡二叉树
题目链接：110.平衡二叉树
文档讲解： 代码随想录
平衡二叉树：每个节点的左子树和右子树的高度差不超过1，并且左右子树也都是平衡二叉树。
思路：使用 -1 来标记已经不是平衡二叉树了，在这种情况下，再返回高度无意义。
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if self.getHeight(root) == -1:
return False
else:
return True
def getHeight(self, node):
if not node:
return 0
leftHeight = self.getHeight(node.left)
if leftHeight == -1:
return -1
rightHeight = self.getHeight(node.right)
if rightHeight == -1:
return -1
#判断是否左右子树深度相差不超过1
if abs(leftHeight - rightHeight) > 1:
return -1
else:
return 1 + max(leftHeight, rightHeight)
递归精简版：
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.getHeight(root) != -1
def getHeight(self, node):
if not node:
return 0
left = self.getHeight(node.left)
right = self.getHeight(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
迭代法:
这道题需要通过求传入节点为根节点的最大深度来求高度，采用后序遍历的方式，求高度不能使用层序遍历，这里使用二叉树的统一迭代方式。
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
st = []
if not root:
return True
st.append(root)
while st:
node = st.pop()
if abs(self.get_height(node.left) - self.get_height(node.right)) > 1:
return False
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
return True
def get_height(self, cur):
stack = []
if cur:
stack.append(cur)
res = 0
depth = 0
while stack:
node = stack.pop()
if node:
stack.append(node)
stack.append(None)
depth += 1
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
else:
stack.pop()
depth -= 1
res = max(res, depth)
return res
迭代精简版：使用字典记录节点的高度。
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
st = []
st.append(root)
height_map = {}
while st:
node = st.pop()
if node:
st.append(node)
st.append(None)
if node.right: st.append(node.right)
if node.left: st.append(node.left)
else:
real_node = st.pop()
left = height_map.get(real_node.left, 0)
right = height_map.get(real_node.right, 0)
if abs(left - right) > 1:
return False
height_map[real_node] = 1 + max(left, right)
return True
3.257. 二叉树的所有路径
题目链接：257. 二叉树的所有路径
文档讲解： 代码随想录
递归法：一定记得要回溯！
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
path = []
if not root:
return res
self.traversal(root, path, res)
return res
def traversal(self, cur, path,res):
#因为不需要遍历到空节点，所以在判断是否为叶子节点前就将该节点存入路径中
path.append(cur.val)
if not cur.left and not cur.right:
spath = '->'.join(map(str, path))
res.append(spath)
return
if cur.left:
self.traversal(cur.left, path, res)
path.pop()#回溯
if cur.right:
self.traversal(cur.right, path, res)
path.pop()
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
path = ''
res = []
if not root:
return res
self.taversal(root, path, res)
return res
def taversal(self, cur, path, res):
path += str(cur.val)
if not cur.left and not cur.right:
res.append(path)
if cur.left:
self.taversal(cur.left, path + '->', res)#隐形回溯，和之前depth + 1是一个道理
if cur.right:
self.taversal(cur.right, path + '->', res)
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
res = []
if not root:
return res
self.traversal(root, [], res)
return res
def traversal(self, cur, path, res):
path.append(cur.val)
if not cur.left and not cur.right:
spath = '->'.join(map(str, path))
res.append(spath)
return
if cur.left:
self.traversal(cur.left, path[:], res)#建立副本，隐形回溯
if cur.right:
self.traversal(cur.right, path[:], res)
迭代法：
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
stack = [root]
path_st = [str(root.val)]
res = []
while stack:
cur = stack.pop()
path = path_st.pop()
if not (cur.left or cur.right):
res.append(path)
if cur.right:
stack.append(cur.right)
path_st.append(path + '->' + str(cur.right.val))
if cur.left:
stack.append(cur.left)
path_st.append(path + '->' + str(cur.left.val))
return res
4.404. 左叶子之和
题目链接：404. 左叶子之和
文档讲解： 代码随想录
难点就是如何判断是否为左叶子节点：必须要通过节点的父节点来判断其左孩子是不是左叶子。如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。采用后序遍历，统计左子树，再统计右子树，最后相加。
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and not root.right:
return 0
leftValue = self.sumOfLeftLeaves(root.left)
#判断左子树是否为左叶子
if root.left and not root.left.left and not root.left.right:
leftValue = root.left.val
rightValue = self.sumOfLeftLeaves(root.right)
summ = leftValue + rightValue
return summ
递归精简版：
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
leaveValue = 0
if root.left and not root.left.left and not root.left.right:
leaveValue = root.left.val
return leaveValue + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
迭代法：
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
stack = []
stack.append(root)
num = 0
while stack:
node = stack.pop()
if node.left and not node.left.left and not node.left.right:
num += node.left.val
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return num
5.可变和不可变类型区分
有两个例子：代码正确与否不论
class Solution():
def preorderTraversal(self, root):
ans = []
def Traversal(root):
if not root: return
ans.append(root.val)
Traversal(root.left)
Traversal(root.right)
Traversal(root)
return ans
class Solution:
def sumofLeftLeaves(self,root):
def isLeftLeaf(root):return root and not root.left and not root.right
res = 0
def dfs(root):
if not root:return 0
if isLeftLeaf(root.left):
res = res + root.left.val
dfs(root.left)
dfs(root)
return res
在运行第二个代码的时候会报错，原因是因为 res 是不可变类型，第一个代码中 ans 可以传入的原因是它是可变类型。
在 Python 中，列表（list）、字典（dict）、集合（set）、字节数组（bytearray）等是可变类型，因为它们的内容可以修改。而整数（int）、浮点数（float）、字符串（str）、元组（tuple）等则是不可变类型，因为它们的值一旦设定就不能更改。
