二叉树
二叉搜索树
二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件：
- 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
- 若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。
它的左、右子树也都是二分搜索树。
如下图所示：
530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3]
输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1
提示：
- 树中节点的数目范围是 [2, 104]
- 0 <= Node.val <= 105
递归法
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
l = self.tree2list(root)# 中序遍历得到有序列表
mindif = 10**6
for i in range(1,len(l)):
mindif = min(mindif,(l[i]-l[i-1]))
return mindif
def tree2list(self,root):
# 中序遍历
if not root:
return []
left = self.tree2list(root.left)
right = self.tree2list(root.right)
return left+[root.val]+right
题目
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入： root = [1,2,2,3,4,4,3]
输出： true
示例 2：
输入： root = [1,2,2,null,3,null,3]
输出： false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
递归
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.compare(root.left,root.right)
def compare(self,left,right):
# 如果左右都是空的，那么说明是对称的
if (not left) and (not right):
return True
# 先判断左右是否有一者没有，然后判断两者是否相等
if left == None or right == None or left.val!=right.val:
return False
# 外侧是否对称
a = self.compare(left.left,right.right)
# 内侧是否对称
b = self.compare(left.right,right.left)
return a and b
迭代法
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
# 把root的左右放入队列，如果没有加入的就是None
queue = collections.deque([root.left,root.right])
while queue:
# 两两取出
left = queue.popleft()
right = queue.popleft()
# 左右不等就不对称
if (not left) and (not right):
continue
# 先判断左右是否有一者没有，然后判断两者是否相等
if (not right) or (not left) or left.val != right.val:
return False
# 分别加入左.左，右.右，左.右，右.左
queue.append(left.left)
queue.append(right.right)
queue.append(left.right)
queue.append(right.left)
return True
二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。（同时没有左右节点）
示例 1：
输入： root = [3,9,20,null,null,15,7]
输出： 2
迭代法
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = collections.deque([root]) # 队列
deep = 0
while queue:
deep+=1
for _ in range(len(queue)):
cur = queue.popleft()
if cur.left:
queue.append(cur.left)
# 当前节点的子节点同时没有左右节点
if (not cur.left.left) and (not cur.left.right):
return deep+1
if cur.right:
queue.append(cur.right)
if (not cur.right.left) and (not cur.right.right):
return deep+1
return deep
递归法
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
# 结束条件1，root为None，返回0
if not root:
return 0
# 结束条件2，子节点都不存在，返回1
if (not root.left) and (not root.right):
return 1
# 结束条件3，如果左子节点为None，返回右节点值
if not root.left:
return self.minDepth(root.right)+1
# 结束条件4，如果左右子节点为None，返回左节点值
if not root.right:
return self.minDepth(root.left)+1
# 如果不是上述条件，比较左右子节点数目，去较小者
deep = min(self.minDepth(root.left),self.minDepth(root.right))
return deep+1
完全二叉树的节点个数
222. 完全二叉树的节点个数 - 力扣（LeetCode）
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入： root = [1,2,3,4,5,6]
输出： 6
递归
# 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 countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return self.countNodes(root.left)+self.countNodes(root.right)+1
每次数量为左节点数+右节点数+本身（1）
迭代法
import collections
class Solution:
def countNodes(self, root: TreeNode) -> int:
queue = collections.deque()
if root:
queue.append(root)
result = 0
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
result += 1 #记录节点数量
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
二叉树的所有路径
257. 二叉树的所有路径 - 力扣（LeetCode）
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入： root = [1,2,3,null,5]
输出： ["1->2->5","1->3"]
示例 2：
输入： root = [1]
输出： ["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
遍历
# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
# 定义一个栈，存放路径
path_list = [str(root.val)]
# 定义一个栈，放当前节点，先处理当前节点及其子节点路径，后进先出
stack = [root]
# 存放结果
res = []
while stack:
cur = stack.pop()
path = path_list.pop()
# 如果当前节点的子节点没有元素，说明是路径的最后一站
if (not cur.left) and (not cur.right):
res.append(path)
# 放入子节点元素
if cur.left:
stack.append(cur.left)
# 放入路径
path_list.append(path+'->'+str(cur.left.val))
if cur.right:
stack.append(cur.right)
path_list.append(path+'->'+str(cur.right.val))
return res
路径总和
112. 路径总和 - 力扣（LeetCode）
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入： root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出： true
**解释：**等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入： root = [1,2,3], targetSum = 5
输出： false
解释： 树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入： root = [], targetSum = 0
输出： false
解释： 由于树是空的，所以不存在根节点到叶子节点的路径。
递归法
迭代时不停地在targetSum中减去当前节点的值，如果到最后一个节点时剩余值与节点值相等，返回True
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# 空二叉树，返回False
if not root:
return False
return self.haveEqual(root,targetSum)
def haveEqual(self,cur,count):
# cur 当前节点
# count targetSum-路径节点值的剩余值
# 如果左右子节点为空且剩余值与节点值相等，返回True
if (not cur.left) and (not cur.right) and count==cur.val:
return True
# 如果左右子节点为空，但剩余值与节点值不等，返回False
if (not cur.left) and (not cur.right):
return False
# 减去当前节点值
count = count-cur.val
# 初始化值为False，当有一个值为True，返回True
left = right = False
if cur.left:
left = self.haveEqual(cur.left,count)
if cur.right:
right = self.haveEqual(cur.right,count)
return left or right
迭代法
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
stack = [root] # 栈1，存放二叉树节点，后进先出
sums_list = [root.val] # 栈2，存放二叉树开始到栈1节点和的列表
while stack:
cur = stack.pop()。 # 当前节点
sums = sums_list.pop() # 到当前节点的和
# 如果当前元素左右子节点都不在，且到当前节点的和与所给值相等，返回True
if (not cur.left) and (not cur.right) and sums==targetSum:
return True
if cur.right:
stack.append(cur.right)
sums_list.append(sums+cur.right.val)
if cur.left:
stack.append(cur.left)
sums_list.append(sums+cur.left.val)
return False
路径总和
113. 路径总和 II - 力扣（LeetCode）
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出： [[5,4,11,2],[5,8,4,5|5,4,11,2],[5,8,4,5]]
迭代法
# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
stack = [root] # 栈1，存放二叉树节点，后进先出
res = []
path_list=[[root.val]]
while stack:
cur = stack.pop() # 当前节点
path = path_list.pop()
# 如果当前元素左右子节点都不在，且到当前节点的和与所给值相等，返回path
if (not cur.left) and (not cur.right) and sum(path)==targetSum:
res.append(path)
if cur.right:
stack.append(cur.right)
path_list.append(path+[cur.right.val])
if cur.left:
stack.append(cur.left)
path_list.append(path+[cur.left.val])
# print(path_list)
return res
代码中的path_list变化：
[[5]]
[[5, 8], [5, 4]]
[[5, 8], [5, 4, 11]]
[[5, 8], [5, 4, 11, 2], [5, 4, 11, 7]]
[[5, 8], [5, 4, 11, 2]]
[[5, 8]]
[[5, 8, 4], [5, 8, 13]]
[[5, 8, 4]]
[[5, 8, 4, 1], [5, 8, 4, 5]]
[[5, 8, 4, 1]]
[]
递归法
- 本人做法， 其中递归时重新定义path，占内存，不然只append的话会造成path内包括所有元素
# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
res = []
# 存放路径
path = []
self.getSum(root, path, res, targetSum)
return res
def getSum(self, cur, path, res,targetSum):
path = path+[cur.val] # 重新定义path，占内存，不然只append的话
# print(path)
if (not cur.left) and (not cur.right) and sum(path)==targetSum:
res.append(path)
if cur.left:
self.getSum(cur.left,path,res,targetSum)
if cur.right:
self.getSum(cur.right,path,res,targetSum)
- 代码随想录做法 Python部分)，很巧妙的对path先append()，后pop()
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
result = []
self.traversal(root, targetSum, [], result)
return result
def traversal(self,node, count, path, result):
if not node:
return
path.append(node.val)
count -= node.val
if not node.left and not node.right and count == 0:
result.append(list(path))
self.traversal(node.left, count, path, result)
self.traversal(node.right, count, path, result)
path.pop()
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
迭代法
- 停止条件
如果当前节点等于p或者q，或者节点为空，返回节点本身
if root==p or root==q or (not root):
return root
- 递归逻辑
采用后序遍历，根据左右子树的返回值，处理中节点的逻辑
如果左右节点有返回值，那么说明该节点及其子节点存在p或者q
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root==p or root==q or (not root):
return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if left and right:
return root
if not left:
return right
return left
删除搜索二叉树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
提示:
- 节点数的范围
[0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>- 节点值唯一
root是合法的二叉搜索树-10<sup>5</sup> <= key <= 10<sup>5</sup>
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
迭代法
# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root is None:
return root
dummy = root
pre = None
while root:
if root.val>key:
pre = root
root = root.left
elif root.val<key:
pre = root
root =root.right
else:
break
# 如果pre为None，代表在根节点root.val==key
if pre is None:
return self.deleteOneNode(root)
else:
# 分清楚删除的节点是前一个节点的左节点还是右节点
if pre.val>key:
pre.left = self.deleteOneNode(root)
if pre.val<key:
pre.right = self.deleteOneNode(root)
return dummy
def deleteOneNode(self,target):
if target is None:
return None
elif target.right is None:
return target.left
elif target.left is None and target.right is not None:
return target.right
else:
cur = target.right
while cur.left:
cur = cur.left
cur.left = target.left
return target.right