学习资料：https://programmercarl.com/0110.平衡二叉树.html#算法公开课
平衡二叉树：任意一个节点的左右子树高度差不超过1
左叶子：是叶子节点，且是其父节点的左节点
完全二叉树：上层均满，底层的节点从左到右连续
满二叉树：每层都是满的，节点总数为 (2^k + 1)
语法： 2<<1 是 2^2
学习记录：
110.平衡二叉树 （巧：当发现这个节点不平衡后，返回-1，再向上依次传递-1）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
node_height = self.getHeight(root)
if node_height != -1:
return True
else:
return False
def getHeight(self, node):
"""
递归法+后序遍历
对于平衡二叉树而言，计算高度函数的逻辑是：
当节点左右子树高度差超过1则该节点为不平衡，高度记为-1，则向上传递时，该节点作为上面的子树一直传递-1即可；
而当节点左右子树高度不超过1，则记录节点的真实高度，即1+max(左右子树)
"""
if not node:
return 0
left_h = self.getHeight(node.left)
if left_h == -1:
return -1
right_h = self.getHeight(node.right)
if right_h == -1:
return -1
if abs(left_h-right_h)>1:
node_h = -1
else:
node_h = 1 + max(left_h, right_h)
return node_h
257.二叉树的所有路径（递归+回溯）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def traversal(self, node, path, result):
"""
前序遍历+回溯+递归
"""
path.append(node.val) # 存放当下考虑的节点，后面要弹出，相当于回到上一个节点
if not node.left and not node.right: # 叶子节点
sPath = '->'.join(map(str, path))
result.append(sPath)
return
if node.left:
self.traversal(node.left, path, result) # 递归
path.pop() # 回溯，每考虑完一个节点就要返回到上一个节点
if node.right:
self.traversal(node.right, path, result)
path.pop()
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
result = []
path = []
if not root:
return result
self.traversal(root, path, result) # 因为list可以传递，traversal就不返回值了，只要处理list就行
return result
404.左叶子之和（判断一个节点是否为左叶子，要在它的父节点处判断；后序遍历）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 如果节点是Null，那它没有左叶子
if not root:
return 0
# 如果节点是叶子，那它没有左叶子
if not root.left and not root.right:
return 0
# 那剩余情况的节点都有左叶子
# 开始后序遍历，左右根，递归法
# 左：节点的左子树中的左叶子的值
left_num = self.sumOfLeftLeaves(root.left) # 递归
if root.left and not root.left.left and not root.left.right: # 此节点root是判断它的左子节点root.left是否为左叶子(是叶子节点，且，为父节点的左子节点)
left_num = root.left.val # 提取左叶子的值
# 右：节点的右子树的左叶子的值
right_num = self.sumOfLeftLeaves(root.right)
# 根：节点左子树的左叶子的值和右子树的左节点的值求和
sum_num = left_num + right_num
return sum_num
222.完全二叉树的节点个数（对于完全二叉树有个特殊解法，找到其中的满二叉树，那下面的直接2^k-1就算出来了；后序遍历）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 后序遍历+递归法
# 终止条件1：node为null
if not root:
return 0
# 终止条件2：找到其中的满二叉树，这部分的节点数可用公式(2^k + 1)计算
left = root.left
right = root.right
left_depth = 0
right_depth = 0
while left: # 遍历root左子树的所有左节点
left = left.left
left_depth += 1
while right: # 遍历root右子树的所有右节点
right = right.right
right_depth += 1
if left_depth == right_depth: # 在完全二叉树的基础上，当左侧深度等于右侧深度，则此部分为满二叉树
return (2 << left_depth) - 1 # 语法 2<<1是2^2，所以上面深度初始值记为0
# 处理逻辑：后序，左右根
left_num = self.countNodes(root.left) # 当不是完全二叉树时，就向节点的左右子树递归，
right_num = self.countNodes(root.right)
total_num = left_num + right_num + 1
return total_num
PS:今天的有点费脑子，有点尝到递归的味道了，好像听懂了又好像没听懂，就感觉递归很方便
今天吃到了好吃的外卖，有锅气的土豆肉丝炒饭，和面泡软了的牛肉拉面
又是被审判的一次面试，是不是找不到工作了，我严重怀疑
勒！