整体的逻辑是在当前节点进行左右子树的迭代
基础stopcase: 上一个节点为叶子结点，本次node为空
二叉树深度
DFS 后序遍历
- stopcase是当前为null，返回0
- 当前node的深度为 max（左深度，右深度）+ 自己1
class Solution:
def maxDepth(self, root: TreeNode) -> int:
# stopcase
if not root:
return 0
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
# 实际深度是左右两个子树，深的那个+1（本节点）
return max(left_depth,right_depth)+1
BFS 层序遍历
- 使用queue来实现，每遍历一层，depth+1
- 直到遍历完成，返回depth
- queue存的当上一层所有的node，依次pop并记录它们的children
- 把这些children放到cur_row里面，等queue空了之后替代queue；depth+=1
- 直到cur_row空了，queue空了，遍历完成，直接返回depth
class Solution:
def maxDepth(self, root: TreeNode) -> int:
# basecase
if not root: return 0
queue = [root]
cur_depth = 0
while queue:
cur_row = [] # 记录本层的所有node
for node in queue: # 把上一层的所有子节点放到本层的list里
if node.left: cur_row.append(node.left)
if node.right: cur_row.append(node.right)
# 更新queue为本层的node list
queue = cur_row
# 深度+1
cur_depth += 1
return cur_depth
判断是否为平衡二叉树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
- 自底向上的进行判断，对于某个节点，如果不平衡返回-1；以此进行剪枝
- 方法同二叉树找深度，如果左右任一深度为-1，剪枝，直接返回-1
- 进行当前节点的平衡判断，如果平衡return 深度，否返回-1
- 最终root的return值如果是-1即为不平衡，其他值即为平衡
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def recur(root):
# stop case
if not root:
return 0
# 利用-1 剪枝
left_depth = recur(root.left)
right_depth = recur(root.right)
if left_depth == -1 or right_depth == -1:
return -1
# 当前阶段不平衡
elif abs(left_depth - right_depth) > 1:
return -1
# 当前节点平衡了，把depth return
else:
return max(left_depth,right_depth)+1
return recur(root)!= -1
二叉树中和为某值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
- 迭代参数：当前节点，剩余的targetsum
- 停止条件：当前为叶子且剩余target = 0
- 整体思路：通过recur函数遍历并记录所有的path，通过剩余target来确认是否是要找的那条，如果是，直接append到result里面
有点不明白path.pop()的作用和逻辑
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
result = []
path = []
def recur(node, tar):
# 终止情况1: 上一个是叶节点，本次node为空
if not node:
return
# 否则正常把当前值放到path里面，并且计算余下的target
path.append(node.val)
tar -= node.val
# 终止条件：如果不剩tar了，且当前是叶子节点，返回path
if tar == 0 and not node.left and not node.right:
result.append(list(path))
path.pop()
else: # 继续迭代
recur(node.left,tar)
recur(node.right,tar)
path.pop()
recur(root,target)
return result
二叉树转双向列表（有序）
- 有序的实现方式为中序遍历（左、根、右）
def dfs(root):
if not root: return
dfs(root.left) # 左
print(root.val) # 根
dfs(root.right) # 右
- 通过pre，cur指针构建双向列表；pre.right = cur cur.left = pre; 更新 cur = pre
- 全局变量self.pre用于记录上一个点的信息，每次更新迭代
"""
# Definition for a Node.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
# 初始化pre指针
self.pre = None
self.head = None
def dfs(cur):
if not cur:
return
dfs(cur.left) # 左子树
# 对于当前节点，构建到双向链表中
if not self.pre: # 如果是第一个，记录一下head
self.head = cur
else: # 构建，插入进去
self.pre.right = cur
cur.left = self.pre
# 更新全局变量pre
self.pre = cur
dfs(cur.right) # 右子树
if not root: return #如果树为空，返回空
dfs(root)
self.head.left, self.pre.right = self.pre, self.head # 最终首尾相连（pre是最后一个元素）
return self.head
二叉搜索树的第 k 大节点
- 中序倒叙遍历(右中左)，记录index，第k个直接返回
- 注意如果是 k-= 1， 第k个时， k=1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
if not root or self.index <= 0:return
dfs(root.right)
if self.index == 1:
self.result = root.val
self.index -= 1
dfs(root.left)
self.index = k
self.result = None
dfs(root)
return self.result
二叉树最近的公共祖先
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
- p、q公共祖先有且仅有三种情况
** p、q分别在一个node的左右两个子树中
** q=root，p在q的某个子树中
** p=root，q在p的某个子树中
