-
前序遍历
-
114 二叉树展开为链表
-
129 求根节点到叶节点数字之和
-
144 二叉树的前序遍历
-
257 二叉树的所有路径
-
589 N 叉树的前序遍历
-
606 根据二叉树构建字符串
-
653 两数之和 IV
-
671 二叉树中第二小的节点
-
872 叶子相似的树
-
965 单值二叉树
-
-
后序遍历
- 104 二叉树的最大深度
- 110 平衡二叉树
- 111 二叉树的最小深度
- 112 路径总和
- 113 路径总和 II
- 124 二叉树中的最大路径和
- 145 二叉树的后序遍历
- 222 完全二叉树的节点个数
- 226 翻转二叉树
- 236 二叉树的最近公共祖先
- 404 左叶子之和
- 543 二叉树的直径
- 559 N 叉树的最大深度
- 563 二叉树的坡度
- 590 N 叉树的后序遍历
- 652 寻找重复的子树
- 687 最长同值路径
-
层次遍历
- 102 二叉树的层序遍历
- 103 二叉树的锯齿形层序遍历
- 107 二叉树的层序遍历 II
- 116 填充每个节点的下一个右侧节点指针
- 117 填充每个节点的下一个右侧节点指针 II
- 199 二叉树的右视图
- 429 N 叉树的层序遍历
- 513 找树左下角的值
- 515 在每个树行中找最大值
- 637 二叉树的层平均值
- 662 二叉树最大宽度
-
中序遍历/二叉搜索树
- 94 二叉树的中序遍历
- 95 不同的二叉搜索树 II
- 98 验证二叉搜索树
- 99 恢复二叉搜索树
- 173 二叉搜索树迭代器
- 230 二叉搜索树中第K小的元素
- 235 二叉搜索树的最近公公祖先
- 450 删除二叉搜索树中的节点
- 501 二叉搜索树中的众数
- 530 二叉搜索树的最小绝对差
- 538 把二叉搜索树转换为累加树
- 669 修剪二叉搜索树
- 700 二叉搜索树中的搜索
- 701 二叉搜索树中的插入操作
- 783 二叉搜索树节点最小距离
-
二叉树的构造
所有构造提都是通过左子树，右子树的节点数来控制递归的深度，只不过得到节点数的方式不同
- 105 从前序与中序遍历序列构造二叉树：前序定位root，中序划分左右子树
- 106 从中序与后序遍历序列构造二叉树：后序定位root，中序划分左右子树
- 108 将有序数组转换为二叉搜索树：前序
- 109 有序链表转换二叉搜索树：中序
- 623 在二叉树中增加一行：后序
- 654 最大二叉树
- 889 根据前序和后序遍历构造二叉树：前序定位root，后序定位左子树节点数
-
二叉树双指针
- 100 相同的树
- 101 对称二叉树
- 572 另一棵树的子树
- 617 合并二叉树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104
# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
def helper(p,q):
if not p and not q:
return True
elif not q or not p:
return False
elif p.val != q.val:
return False
else:
return helper(p.left, q.left) and helper(p.right, q.right)
result = helper(p,q)
return resultTips
- 同样是递归的解法
- 停止条件就是p!=q, 或者都是空返回True
- 执行就是遍历左子树/右子树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
- 递归
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def helper(left, right):
if not left and not right:
return True
elif not left:
return False
elif not right :
return False
elif left.val != right.val:
return False
else:
return helper(left.left, right.right) and helper(left.right, right.left)
res = helper(root.left, root.right)
return res - 迭代: 很直观直接用栈复现递归背后的逻辑即可
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
stack = [root.left, root.right]
while stack:
right = stack.pop()
left = stack.pop()
if not left and not right:
continue
elif not left:
return False
elif not right :
return False
elif left.val != right.val:
return False
else:
stack.append(right.left)
stack.append(left.right)
stack.append(right.right)
stack.append(left.left)
return True Tips
- 递归：可以和前一题相同的树进行类比，只不过上一题递归处理的事两个树相同位置的pointer，这里是一棵树对称位置的pointer
- 迭代：成对的把节点入栈，再成对的出栈进行判断
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例： 二叉树：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层序遍历结果：
[ [3], [9,20], [15,7] ]
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
if not root:
return result
stack = [root]
while stack:
tmp = []
for i in range(len(stack)):
node = stack.pop(0)
tmp.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
result.append(tmp)
return result 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如： 给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层序遍历如下：
[ [3], [20,9], [15,7] ]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 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 zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
result = []
cur_level = [root]
flag = 1
while cur_level:
next_level = []
cur_value = []
for i in cur_level:
cur_value.append(i.val)
if i.left:
next_level.append(i.left)
if i.right:
next_level.append(i.right)
cur_level = next_level
if flag>0:
result.append(cur_value)
else:
result.append(cur_value[::-1])
flag *=-1
return result - 和层次遍历相同就是多加一层用于reverse列表即可
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
- 递归
# 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 maxDepth(self, root: TreeNode) -> int:
def helper(root):
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
return max(left, right) + 1
depth = helper(root)
return depth - 迭代
class Solution:
def maxDepth(self, root: TreeNode) -> int:
depth = 0
if not root:
return depth
stack = [root]
while stack:
n = len(stack)
depth+=1
for i in range(n):
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return depthTips
- DFS的递归解法, 其实是后序遍历，因为要收集叶子结点的depth信息， 时间是O(n)因为每个节点只访问一次，空间复杂度是O(height)递归会把经过节点压入栈中，
- 终止条件是叶节点
- 返回是每次的depth+1，叶节点返回0
- 执行是每一步都求左边/右边的max_depth
- 迭代法采用层次遍历就好
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1] Output: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def dfs(start,end):
if start>end:
return None
root = preorder.pop(0)
pos =inorder.index(root)
root=TreeNode(root)
root.left = dfs(start, pos-1)
root.right = dfs(pos+1, end)
return root
root =dfs(0,len(preorder)-1)
return root Tips
- 前序遍历会从左向右访问根结点
- 中序遍历其实你用来找左子树和右子树分别有多少个节点的
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def dfs(start, end):
if start>end:
return None
root = postorder.pop()
pos = inorder.index(root)
root = TreeNode(root)
root.right = dfs(pos+1, end)
root.left = dfs(start, pos-1)
return root
root = dfs(0, len(inorder)-1)
return root - 后序遍历的顺序保证了从后向前遍历，每个点都是（右->左）的前序遍历，也就是会最先访问到根结点。然后找到根结点再中序遍历中的位置切分左子树和柚子树即可。注意这里要先右后左，和后序遍历的递归写法一致。
- 这里和二分法相同需要注意边界。方法就是区间要统一，这里用的是左右都是闭区间（都能在list里面访问到），所以pos所在的位置时根结点，要在左和右区间中都做剔除，左边是[start,pos-1]，右边是[pos+1, end]。因为都是闭区间，所以最后允许start==end，停止条件就是start>end，输入的参数就是[0,len-1]
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如： 给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其自底向上的层序遍历为：
[ [15,7], [9,20], [3] ]
# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
stack = [root]
ans = []
while stack:
tmp = []
for i in range(len(stack)):
node = stack.pop(0)
tmp.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
ans.append(tmp)
return ans[::-1]Tips
层次遍历再反转结果
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3] 输出：[3,1] 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def helper(left, right):
if left > right:
return None
mid = (left+right)//2
root = TreeNode(nums[mid])
root.left = helper(left, mid-1)
root.right = helper(mid+1,right)
return root
tree = helper(0, len(nums)-1)
return tree Tips
- 二叉搜索树，是left<root<right，中序遍历会得到递增序列
- 创建方式就是不断寻找mid，作为root，然后笑的部分做left，大的部分做right
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9 / /
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 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 sortedListToBST(self, head: ListNode) -> TreeNode:
cur = head
length =0
while cur:
cur = cur.next
length +=1
def build_bst(start,end):
nonlocal head
if start > end:
return None
mid = (start+end)//2
left = build_bst(start,mid-1)
root = TreeNode(head.val )
head = head.next
root.left = left
right = build_bst(mid+1, end)
root.right = right
return root
tree = build_bst(1,length)
return treeTips
- 链表的遍历是单调的，二叉搜索树的中序遍历也是单调的，二者一拍即合。一边做中序遍历，一边向前遍历链表，这样就和把有序数组转换成二叉搜索树一样了， 只不过有序数组是取nums[mid]，后者是向前遍历的链表
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
# 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 isBalanced(self, root: TreeNode) -> bool:
def helper(root):
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
if abs(left-right)>1:
return - 1
elif left ==-1 or right==-1:
return -1
else:
return max(left, right)+1
balance = helper(root)
return balance!=-1
Tips
- 看到题第一反应就是和求二叉树最大深度是一个意思，但问题在于在计算height的同时需要判断是否balanc！所以需要思考如何把是否balance的判断融合到depth的计算当中，并且只要子树存在balance=0,这个判断需要一直被回传到top
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
提示：
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000
# 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: TreeNode) -> int:
def helper(root):
if not root:
return 0
elif not root.left and not root.right:
return 1
elif not root.left:
return helper(root.right)+1
elif not root.right:
return helper(root.left)+1
else:
left = helper(root.left)
right = helper(root.right)
return min(left, right)+1
depth = helper(root)
return depth Tips
- 这题和104二叉树的最大深度相比存在一些不同。最开始第一个念头是直接把那道题的max变成min不就齐活了？后来发现最大问题min不满足叶子结点这一命题，如果node只有右子树，则求min会得到1，但这时node不是leaf所以不满足条件。和最大深度区别在于，需要判断leaf，以及在只有左/右子树的时候进行区别处理
- 解决方案依旧是用min，不过需要加入对叶子结点，以及有/无左/右子树的判断判定
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 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
示例 3：
输入：root = [1,2], targetSum = 0 输出：false
提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
# 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:
def helper(root, target):
if not root:
return False
if not root.left and not root.right:
return root.val==target
return helper(root.left, target-root.val) or helper(root.right, target - root.val)
res =helper(root, targetSum)
return res tips
- 递归解法，终止条件有两个，进入叶节点判断剩余target==val ，进入None，这时因为=并非是叶节点所以返回False
给你二叉树的根节点 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]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
# 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]]:
result = []
if not root:
return []
def dfs(node, path, target):
nonlocal result
if not root:
return
if not node.left and not node.right:
if target ==node.val:
result.append(path+[node.val])
return
if node.left:
dfs(node.left, path+[node.val], target-node.val)
if node.right:
dfs(node.right, path+[node.val], target-node.val)
dfs(root, [], targetSum)
return result Tips
路经综合1的升级版，需要返回所有=target的路径，而非只是判断是否有这样一条路径。只需要多加入一个全局变量来统计所有path即可
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
- 递归解法，先生成orderlist，再构建link 空间复杂度O(n)
这里的链表实际是一棵只有右子树没有左子树的Tree。以上遍历方式就是前序遍历，所以直接用前序遍历把节点按顺序存储，在依次取出构建link
# 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 flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
firstorder = []
def helper(root):
if not root:
return
firstorder.append(root)
helper(root.left)
helper(root.right)
helper(root)
for i in range(1,len(firstorder)):
pre, cur = firstorder[i-1], firstorder[i]
pre.left = None
pre.right = cur - 迭代解法， 一遍遍历，一遍构建，空间复杂度O(n)
前序遍历+pre节点构建链表：其实只需要保留前驱节点，就可以一边遍历一遍重新构建link。但因为相当于用pre重新构建了新的链表所以空间复杂度是O(n)
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return root
stack = [root]
pre = None
while stack:
node = stack.pop()
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
if not pre:
pre = node
else:
pre.left = None
pre.right=node
pre = pre.right
return root - 递归算法：空间复杂度O(h)
想要降低空间复杂度就只能在原先的tree结构上改变link，只用指针保留前驱节点。空间复杂度等于栈的深度也就是O(h)。
注意因为要先修改右边节点所以遍历顺序是右/左中
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
pre = None
def dfs(root):
nonlocal pre
if not root:
return
dfs(root.right)
dfs(root.left)
root.left = None
root.right = pre
pre = root
dfs(root)
return pre 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
提示：
树中节点的数量少于 4096
-1000 <= node.val <= 1000
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
stack = [root]
while stack:
n = len(stack)
for i in range(n):
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
if i==n-1:
node.next = None
else:
node.next = stack[0]
return root Tips
层次遍历，和右视图有些像，都是把最右边的一个找出来特殊处理
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
提示：
树中的节点数小于 6000
-100 <= node.val <= 100
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
stack = [root]
while stack:
n = len(stack)
for i in range(n):
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
if i==n-1:
node.next = None
else:
node.next = stack[0]
return root 虽然不是完美树，但是对解法并没有影响
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
res = -1000
def dfs(root):
nonlocal res
if not root:
return 0
left = max(dfs(root.left),0)
right = max(dfs(root.right),0)
res = max(res, left+right+root.val)
return max(left,right)+root.val
dfs(root)
return res Tips
和二叉树的最大直径相比只有一个差异，就是可以从任意节点开始从任意节点结束。所以对是否选择左/右子树存在灵活性，如果<0就不选择，处理方式也很简单只保留>-=0的部分即可
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 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 preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
def helper(root):
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res - 迭代
迭代的思路是按返回顺序倒叙入栈（因为栈是FILO）
中左右，所以是每个遍历到的node，val直接加入result，然后右边入栈，左边入栈
个人感觉前序遍历迭代是最好写的，因为中在前， 所以第一个元素的写入和遍历顺序一致
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res 给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [3,2,1]
- 递归
# 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 postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
def helper(root):
if not root:
return
helper(root.left)
helper(root.right)
res.append(root.val)
helper(root)
return res - 迭代
因为中在最后，和遍历顺序不一致的因素，所以后序遍历直接写并不好写。但你会发现把后序遍历的结果reverse，就是前序遍历但是左右颠倒，也就是中右左的结果！
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
stack =[root]
while stack:
cur =stack.pop()
res.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
return res[::-1]Tips
- 二叉树的后续遍历可用于求当前节点所有child之和，用于例如左子叶之和，二叉树的坡度等题
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
示例：
输入 ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 输出 [null, 3, 7, true, 9, true, 15, true, 20, false]
解释 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 9 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 15 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 20 bSTIterator.hasNext(); // 返回 False
提示：
树中节点的数目在范围 [1, 105] 内
0 <= Node.val <= 106
最多调用 105 次 hasNext 和 next 操作
进阶：
你可以设计一个满足下述条件的解决方案吗？next() 和 hasNext() 操作均摊时间复杂度为 O(1) ，并使用 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 BSTIterator:
def __init__(self, root: TreeNode):
self.root = root
self.stack = []
while self.root:
self.stack.append(self.root)
self.root = self.root.left
def next(self) -> int:
cur = self.stack.pop()
node = cur.right
while node:
self.stack.append(node)
node = node.left
return cur.val
def hasNext(self) -> bool:
return len(self.stack)>0
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()Tips
用迭代方案实现二叉搜索树的中序遍历，每一次迭代都是遍历所有的左节点。
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
二叉树的节点个数的范围是 [0,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 rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
n = len(stack)
for i in range(n):
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
if i == n-1:
ans.append(node.val)
return ans Tips
层次遍历
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
- 正常后序遍历: 复杂度是O(n)
# 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: TreeNode) -> int:
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
return left+right+1
return dfs(root)Tips
-
递归，后序遍历，和depth问题类似，depth问题是左右取min/max+1。节点数问题只要相加就好
-
应用满二叉树性质进行地柜的方案，复杂度是O（logn^2）O(树深度^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 countNodes(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return 0
lh,rh = 0,0
left = root
right = root
while left:
left = left.left
lh +=1
while right:
right = right.right
rh +=1
if lh==rh:
return 2**lh-1
return dfs(root.right) + dfs(root.left) + 1
return dfs(root)
Tips
利用满二叉树性质，只有最后一层的节点可能不满，所以只有当左树深度！=右树深度时候需要进一步递归检查，否则可以直接返回当前树的节点数。每一步都是O（树深度）的复杂度，最差情况需要遍历O(树深度次)
翻转一棵二叉树。
示例：
输入：
4
/
2 7
/ \ /
1 3 6 9
输出：
4
/
7 2
/ \ /
9 6 3 1
# 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 invertTree(self, root: TreeNode) -> TreeNode:
def helper(root):
if not root:
return root
#这里不能直接赋值，会导致乐翻天
root.left, root.right = helper(root.right), helper(root.left )
return root
root = helper(root)
return root pTips
- 注意递归中的返回值
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
提示：
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
- 递归解法
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
counter =0
ans =0
def dfs(root):
nonlocal counter,ans
if not root:
return
dfs(root.left)
counter+=1
if counter==k:
ans = root.val
return
dfs(root.right)
dfs(root)
return ans - 迭代解法
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k-=1
if k==0:
return root.val
root = root.right Tips
中序遍历，从小到大搜索，等到第K 个元素的时候更新全局变量
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
- 迭代
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val < p.val and root.val <q.val:
root = root.right
elif root.val > p.val and root.val >q.val:
root = root.left
else:
break
return root- 递归
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(root, p, q):
if not root:
return root
if root.val >p.val and root.val > q.val:
return dfs(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return dfs(root.right, p, q)
else:
return root
node = dfs(root, p,q)
return node Tips
-
迭代需要用到搜索树的性质，left <node < right, 如果ab有共同祖先，则一定是q<node<p,所以只需要遍历知道node的val在q/p之间即可
-
递归，和迭代思路一样当遇到在中间的节点返回就好，否则继续按某一方向进行搜索
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 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
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def dfs(root, p, q):
if not root:
return None
if root == q or root==p:
return root
left = dfs(root.left, p,q)
right = dfs(root.right, p, q)
if left and right:
return root
elif left:
return left
else:
return right
node = dfs(root, p, q)
return node Tips
- 因为是公共祖先，所以要从下往上寻找，所以确定是后序遍历。
- 停止条件是遍历到空节点，或者找到q或者p就返回当前节点
- 每层的便利条件是，如果左子树和右子树返回值都不为空，则返回当前节点因为当前就是祖先，否则返回不为空的节点
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100
- 错误解法：对node的状态忘记判断，not node 无法判断上一个节点是否是叶节点，可能只是没有左子树但是存在右子树
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
all_path = []
def helper(node, path):
if not node:
all_path.append(path)
return
return helper(node.left, path.append(root.val)) or helper(node.right, path.append(root.val))
helper(root,[])
return all_path - 正确解法
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return all_path
all_path = []
def helper(node, path):
if not node.left and not node.right:
all_path.append(path + [str(node.val)])
return
if node.left:
helper(node.left, path +[str(node.val)])
if node.right:
helper(node.right, path+[str(node.val)])
helper(root, [])
return ['->'.join(i) for i in all_path]计算给定二叉树的所有左叶子之和。
示例：
3
/
9 20
/
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
- 递归解法
# 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 sumOfLeftLeaves(self, root: TreeNode) -> int:
def helper(root):
if not root:
return 0
if root.left and not root.left.left and not root.left.right:
return root.left.val + helper(root.right)
return helper(root.left) + helper(root.right)
return helper(root)- 递归：上面的递归不太容易看出来是后序遍历，我们来换种写法
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
def helper(root):
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
if root.left and not root.left.left and not root.left.right:
mid= root.left.val
else:
mid = 0
return left +right + mid
return helper(root)- 其实前序遍历也可以，但是需要用全局变量来保存值。在判断左节点就是左子叶的parent节点上进行累加
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
ans = 0
def dfs(root):
nonlocal ans
if not root:
return 0
if root.left and not root.left.left and not root.left.right:
ans += root.left.val
dfs(root.left)
dfs(root.right)
dfs(root)
return ans- 迭代
class Solution:
def sumOfLeftLeaves(self, root: TreeNode) -> int:
stack = [root]
ans = 0
while stack:
node = stack.pop(0)
if node.left and not node.left.left and not node.left.right:
ans+=node.left.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans Tips
- 递归解法和深度，节点数相同都是后序遍历，只不过想上传递的是左子叶的值。
- 和路径之和类似，只不够要判断节点是左子叶，需要站在parent才能进行判断，既下一个节点是左边且下一个节点是叶节点。以及因为站在parent进行判断
- 迭代解法，层次遍历，找到最左边的节点即可
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
stack = [root]
ans = []
while stack:
cur = []
for i in range(len(stack)):
node= stack.pop(0)
if node.children:
stack.extend(node.children)
cur.append(node.val)
ans.append(cur)
return ans给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
- 两层递归
# 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, targetSum: int) -> int:
if not root:
return 0
def dfs(root, target):
if not root:
return 0
if target==root.val:
mid = 1
else:
mid =0
left = dfs(root.left, target-root.val)
right = dfs(root.right, target-root.val)
return mid+left+right
return dfs(root, targetSum)+self.pathSum(root.left, targetSum)+ self.pathSum(root.right, targetSum)
Tips
- 内层递归就是常规的路径求和，区别在于不再中间停止，只在中间记录等于target的路径进行累加
- 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
- 两层递归
# 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, targetSum: int) -> int:
if not root:
return 0
def dfs(root, target):
if not root:
return 0
if target==root.val:
mid = 1
else:
mid =0
left = dfs(root.left, target-root.val)
right = dfs(root.right, target-root.val)
return mid+left+right
return dfs(root, targetSum)+self.pathSum(root.left, targetSum)+ self.pathSum(root.right, targetSum)
Tips
- 内层递归就是常规的路径求和，区别在于不再中间停止，只在中间记录等于target的路径进行累加
- 外层递归加入是否遍历当前节点的选择，可以遍历可以不遍历，每一步只判断当前节点是否符合要求，并向下一个节点进行递归
给定一个二叉搜索树的根节点 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, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
# 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]:
def dfs(root, key):
if not root:
return None
if root.val==key:
if not root.left and not root.right:
return None
elif not root.right:
return root.left
elif not root.left:
return root.right
else:
node = root.right
while node.left:
node = node.left
node.left = root.left
return root.right
if root.val > key:
root.left = dfs(root.left, key)
if root.val < key:
root.right = dfs(root.right, key)
return root
root = dfs(root, key)
return root给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如： 给定 BST [1,null,2,2],
1
2
/
2
返回[2].
提示：如果众数超过1个，不需考虑输出顺序
- 常规解法需要使用额外内存，用搜索树的中序遍历生成order list，然后就变成在order list里面找众数
# 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 findMode(self, root: TreeNode) -> List[int]:
if not root:
return []
nums = []
def inorder(root):
if not root:
return
inorder(root.left)
nums.append(root.val)
inorder(root.right)
inorder(root)
print(nums)
counter,max_count = 1,1
ans = [nums[0]]
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
counter+=1
else:
counter=1
if counter > max_count:
ans = []
ans.append(nums[i])
max_count = counter
elif counter == max_count:
ans.append(nums[i])
return ans - 不实用额外内存: 一边中序遍历，一边比较当前节点的count，如果超过maxcount重制，如果没有超过append
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
if not root:
return []
nums = []
pre = None
max_count =0
cur_count = 0
def inorder(root):
nonlocal pre, nums, max_count, cur_count
if not root:
return
inorder(root.left)
if pre is None:
pre = root.val
cur_count = 1
elif root.val==pre:
cur_count+=1
else:
cur_count = 1
pre = root.val
if cur_count==max_count:
nums.append(pre)
elif cur_count>max_count:
nums = [pre]
max_count = cur_count
inorder(root.right)
inorder(root)
return nums给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1
迭代
# 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 findBottomLeftValue(self, root: TreeNode) -> int:
stack = [root]
ans = None
while stack:
n = len(stack)
for i in range(n):
node = stack.pop(0)
if i==0:
ans = node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ans
Tips
- 用迭代解法很容易解决，就每次都保留新的一行的第一个元素就好，最后一个返回的就是最左边的
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/
3 2
/ \ \
5 3 9
示例2：
输入: root = [1,2,3]
输出: [1,3]
解释:
1
/
2 3
示例3：
输入: root = [1] 输出: [1]
示例4：
输入: root = [1,null,2]
输出: [1,2]
解释:
1
2
示例5：
输入: root = [] 输出: []
提示：
二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1
# 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 largestValues(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
ans = []
while stack:
cur = -2**32
for i in range(len(stack)):
node = stack.pop(0)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
if node.val > cur:
cur = node.val
ans.append(cur)
return ans Tips
层次遍历
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
输入：
1
3
/
2
输出： 1
解释： 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
提示：
树中至少有 2 个节点。
本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
# 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 getMinimumDifference(self, root: TreeNode) -> int:
pre = -2**32
min_dist = 2**32-1
def inorder(root):
nonlocal pre, min_dist
if not root:
return
inorder(root.left)
min_dist = min(min_dist, root.val-pre)
pre = root.val
inorder(root.right)
inorder(root)
return min_dist Tips
- 因为是搜索树，所以用中序遍历，一次计算每一步当前节点-上一个节点的差取min，就一定是最小距离，因为中序遍历是单调的。
- Pre_node需要初始化
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1] 输出：[1,null,1]
示例 3：
输入：root = [1,0,2] 输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1] 输出：[7,9,4,10]
提示：
树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
# 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 convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
total = 0
def dfs(root):
nonlocal total
if not root:
return
dfs(root.right)
root.val += total
total = root.val
dfs(root.left)
dfs(root)
return root Tips
最开始以为是一道超级复杂的题，后来发现只要把中序遍历的方向反过来，从大到小遍历直接累加就是结果。。。
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
diag = 0
def helper(root):
nonlocal diag
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
diag = max(diag, left+right)
return max(left, right) + 1
helper(root)
return diagTips
- 和二叉树的最大深度一个思路，每个节点依旧保留当前左右子树的最大深度，在此基础上多加一步每个节点的半径计算，并更新global变量
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
提示：
树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
max_depth = 0
def helper(root):
if not root:
return 0
if not root.children:
return 1
return max([helper(i) for i in root.children])+1
return helper(root)class Solution:
def maxDepth(self, root: 'Node') -> int:
max_depth = 0
def helper(root):
if not root:
return 0
cur_depth = 0
for i in root.children:
cur_depth = max(cur_depth, helper(i))
return cur_depth +1
return helper(root)Tips
- 和二叉树最大深度基本是一样的，唯一要注意的是多了一个停止条件就是当children为空的时候可以提前返回1 ，不然max里面会报空列表
- 如果要和二叉树停止条件相同，就注意怕奴蛋就好
给定一个二叉树，计算 整个树 的坡度 。
一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。
示例 1：
输入：root = [1,2,3] 输出：1 解释： 节点 2 的坡度：|0-0| = 0（没有子节点） 节点 3 的坡度：|0-0| = 0（没有子节点） 节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ） 坡度总和：0 + 0 + 1 = 1
示例 2：
输入：root = [4,2,9,3,5,null,7] 输出：15 解释： 节点 3 的坡度：|0-0| = 0（没有子节点） 节点 5 的坡度：|0-0| = 0（没有子节点） 节点 7 的坡度：|0-0| = 0（没有子节点） 节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ） 节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ） 节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 16 ） 坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15
示例 3：
输入：root = [21,7,14,1,1,2,2,3,3] 输出：9
提示：
树中节点数目的范围在 [0, 104] 内
-1000 <= Node.val <= 1000
# 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 findTilt(self, root: TreeNode) -> int:
res = 0
def helper(root):
nonlocal res
if not root:
return 0
left = helper(root.left)
right = helper(root.right)
res += abs(left-right)
return left+right+root.val
helper(root)
return res Tips
- 二叉树的后序遍历可类比左子叶之和。递归的停止条件是空，每一步都是向左，向右，然后
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
提示：
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
# 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 isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
def sametree(node1, node2):
if not node1 and not node2:
return True
elif not node1 or not node2:
return False
else:
return node1.val==node2.val and sametree(node1.left, node2.left) and sametree(node1.right, node2.right)
if not root and not subRoot:
return True
if not root or not subRoot:
return False
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) or sametree(root, subRoot) Tips
和相同树一样，变成在root的不同位置判断当前位置的子树是否==subTree
给定一个 N 叉树，返回其节点值的 前序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
进阶：
递归法很简单，你可以使用迭代法完成此题吗?
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[1,3,5,6,2,4]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
提示：
N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内
- 递归解法
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def preorder(self, root: 'Node') -> List[int]:
ans = []
def helper(root):
if not root:
return
ans.append(root.val)
for i in root.children:
helper(i)
helper(root)
return ans
- 迭代解法: 栈先入后出所以children是反序写入的
class Solution:
def preorder(self, root: 'Node') -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
ans.append(node.val)
for i in node.children[::-1]:
stack.append(i)
return ans
给定一个 N 叉树，返回其节点值的 后序遍历 。
N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
进阶：
递归法很简单，你可以使用迭代法完成此题吗?
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[5,6,3,2,4,1]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
提示：
N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内
- 递归法
class Solution:
def postorder(self, root: 'Node') -> List[int]:
ans = []
def helper(node):
if not node :
return
for i in node.children:
helper(i)
ans.append(node.val)
helper(root)
return ans - 迭代法
class Solution:
def postorder(self, root: 'Node') -> List[int]:
if not root:
return []
ans = []
stack = [root]
while stack:
node = stack.pop()
for i in node.children:
stack.append(i)
ans.append(node.val)
return ans[::-1]Tips
后序遍历的技巧在于，把后序遍历的序列反转会得到和前序遍历一样只不过子节点的顺序是从右到左，而非从左到右的序列。所以依旧是前序遍历的解法，只不过反转子节点的写入顺序即可
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
1
/
2 3
/
4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”， 在你省略所有不必要的空括号对之后， 它将是“1(2(4))(3)”。
示例 2:
输入: 二叉树: [1,2,3,null,4]
1
/
2 3
\
4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似， 除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
def dfs(root):
if not root:
return ''
if not root.left and not root.right:
return str(root.val)
res = str(root.val)
left = dfs(root.left)
right = dfs(root.right)
res += '({})'.format(left)
if right:
res+= '({})'.format(right)
return res
return dfs(root)Tips
在前序遍历的基础上，把返回的子树用括号包裹，需要区分三种情况
- 叶节点直接返回值
- 只有左子树，返回值外面用括号包裹
- 只有右子树，左子树是空括号
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
。
# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
def merge(root1, root2):
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = merge(root1.left,root2.left)
root1.right = merge(root1.right, root2.right)
return root1
root = merge(root1, root2)
return root Tips
前序遍历两棵树，针对两个节点是否存在的情况进行判断选择是否相加或者直接返回。
给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。
添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。
将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。
如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。
示例 1:
输入:
二叉树如下所示:
4
/
2 6
/ \ /
3 1 5
v = 1
d = 2
输出:
4
/
1 1
/
2 6
/ \ /
3 1 5
示例 2:
输入:
二叉树如下所示:
4
/
2
/ \
3 1
v = 1
d = 3
输出:
4
/
2
/ \
1 1
/ \
3 1
注意:
输入的深度值 d 的范围是：[1，二叉树最大深度 + 1]。
输入的二叉树至少有一个节点。
# 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 addOneRow(self, root: TreeNode, val: int, depth: int) -> TreeNode:
def dfs(root, val, depth):
if not root:
return
if depth ==1:
node = TreeNode(val)
node.left = root
return node
if depth ==2:
left = TreeNode(val)
right = TreeNode(val)
left.left = root.left
right.right = root.right
root.left = left
root.right = right
return root
dfs(root.left, val, depth-1)
dfs(root.right, val, depth-1)
return root
root = dfs(root, val, depth)
return root 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
3
/
9 20
/
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
if not root:
return []
stack = [root]
ans = []
while stack:
cur = 0
n = len(stack)
for i in range(n):
node = stack.pop(0)
cur+=node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
ans.append(cur/n)
return ans Tips
层次遍历
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树：
2
/
4
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。
# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
counter = defaultdict(int)
ans = []
def dfs(root):
if not root:
return ''
left = dfs(root.left)
right = dfs(root.right)
seralize = '{}.{}.{}'.format(left, right, root.val)
counter[seralize]+=1
if counter[seralize]==2:
ans.append(root)
return seralize
dfs(root)
return ans Tips
- 注意每个重复子树只保留一个，所以判断当counter==2的时候写入
- 后序遍历，递归的返回值是左右子树的序列化表达【依赖不同子树额后序遍历结果是唯一的】，注意这时not root要返回字符串不能返回空
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9 输出: true
示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28 输出: false
示例 3：
输入: root = [2,1,3], k = 4 输出: true
示例 4：
输入: root = [2,1,3], k = 1 输出: false
示例 5：
输入: root = [2,1,3], k = 3 输出: true
提示:
二叉树的节点个数的范围是 [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105
- 前序遍历把每一个遍历过的节点的target-root.val写入hashset，对下一个节点判断是否在hashset中
# 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 findTarget(self, root: TreeNode, k: int) -> bool:
dic = set()
def helper(root):
if not root:
return False
if k-root.val in dic:
return True
dic.add(root.val)
return helper(root.left) or helper(root.right)
return helper(root)- 中序遍历：生成顺序list，然后用二分搜索
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1] 解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同
# 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 constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
def dfs(nums):
if len(nums)==0:
return None
root = TreeNode(max(nums))
pos = nums.index(root.val)
root.left = dfs(nums[:pos])
root.right = dfs(nums[pos+1:])
return root
root = dfs(nums)
return rootTips
树的构造问题，找到root，然后split左右继续递归
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例 1:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
示例 2:
输入:
1
/
3
/ \
5 3
输出: 2 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
示例 3:
输入:
1
/ \
3 2
/
5
输出: 2 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
示例 4:
输入:
1
/ \
3 2
/ \
5 9
/ \
6 7
输出: 8 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。
# 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 widthOfBinaryTree(self, root: TreeNode) -> int:
stack = [(root,0)]
width = 0
while stack:
l = len(stack)
for i in range(l):
node, pos = stack.pop(0)
if i ==0:
left = pos
if i == (l-1):
width = max(width, pos-left+1)
if node.left:
stack.append((node.left, pos*2))
if node.right:
stack.append((node.right, pos*2+1))
return width
Tips
层次遍历，只需要在stack里面加入pos变量表示当前节点的位置，当前root是pos，左子树的位置是pos2, 右子树的pos是2pos+1
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]
示例 3：
输入：root = [1], low = 1, high = 2 输出：[1]
示例 4：
输入：root = [1,null,2], low = 1, high = 3 输出：[1,null,2]
示例 5：
输入：root = [1,null,2], low = 2, high = 4 输出：[2]
提示：
树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
def dfs(root, low, high):
if not root:
return None
if root.val > high:
return dfs(root.left, low, high)
if root.val< low:
return dfs(root.right,low,high)
root.left = dfs(root.left, low,high)
root.right = dfs(root.right,low,high)
return root
root = dfs(root,low,high)
return rootTips
其实比删除节点还要简单，因为不需要对删除后的子树做任何操作，这里只要发现当前节点不符合要求，往符合要求的位置搜索即可。
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，root.val = min(root.left.val, root.right.val) 总成立。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1：
输入：root = [2,2,5,null,null,5,7] 输出：5 解释：最小的值是 2 ，第二小的值是 5 。
示例 2：
输入：root = [2,2,2] 输出：-1 解释：最小的值是 2, 但是不存在第二小的值。
提示：
树中节点数目在范围 [1, 25] 内
1 <= Node.val <= 231 - 1
对于树中每个节点 root.val == min(root.left.val, root.right.val)
# 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 findSecondMinimumValue(self, root: TreeNode) -> int:
ans, rootval = -1, root.val
def helper(root):
nonlocal ans
if not root:
return
if ans !=-1 and root.val > ans:
return
elif root.val > rootval:
ans = root.val
helper(root.left)
helper(root.right)
helper(root)
return ans
Tips
这个二叉树的设定保证了root节点一定是最小的，目标只是找到比root.val大的，比当前ans小的我们就更新ans，否则就返回
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
# 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 longestUnivaluePath(self, root: TreeNode) -> int:
ans = 0
def dfs(root):
nonlocal ans
if not root:
return 0
leftlen = dfs(root.left)
rightlen = dfs(root.right)
curleft = curright = 0
if root.left and root.left.val == root.val:
curleft = leftlen+1
if root.right and root.right.val == root.val:
curright = rightlen+1
ans = max(ans, curleft+curright) # 是最长路径输而非节点数
return max(curleft, curright)
dfs(root)
return ans Tips
- 因为需要和自己诶但比较是否值相同，所以应该是后序遍历，收集左/右子树同值长度的同时，判断是重新计数还是继续累加
- 每一步都更新最长路径长度，并回传左/右更长的路径长度
- 递归操作需要判读啊你当前节点和左/右子树是否相同，如果相同路径+1，不同为0，并更新全局变量的路径长度
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
- 迭代
# 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 searchBST(self, root: TreeNode, val: int) -> TreeNode:
while root and root.val !=val:
if root.val> val:
root=root.left
else:
root=root.right
return root - 递归
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
def search(root):
if not root or root.val== val:
return root
if root.val> val:
return search(root.left)
if root.val < val:
return search(root.right)
return root
result = search(root)
return result Tips
- 因为二叉搜索树有序的性质，所以这道题用迭代反而比用递归更好理解，停止条件就是节点为空或者节点的值=target
- 递归的停止条件和迭代相同，但是在写返回值的时候需要注意，返回的是节点
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5] 解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]
提示：
给定的树上的节点数介于 0 和 10^4 之间
每个节点都有一个唯一整数值，取值范围从 0 到 10^8
-10^8 <= val <= 10^8
新值和原始二叉搜索树中的任意节点值都不同
- 原地修改：需要保留parent节点
# 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 insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
parent = None
if not root:
return TreeNode(val)
def dfs(root, val):
nonlocal parent
if not root:
if parent.val > val:
parent.left = TreeNode(val)
else:
parent.right = TreeNode(val)
return
parent = root
if root.val > val:
dfs(root.left, val)
if root.val < val:
dfs(root.right, val)
dfs(root,val)
return root- 递归修改
class Solution:
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return TreeNode(val)
def dfs(root, val):
if not root:
return TreeNode(val)
if root.val > val:
root.left = dfs(root.left, val)
if root.val < val:
root.right = dfs(root.right, val)
return root
root = dfs(root,val)
return rootTips
- 最简单的做法就是不该动原有的搜索树，只在空节点力加入值，可以有原地修改和递归返回两种解法
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
提示：
树中节点的数目范围是 [2, 100]
0 <= Node.val <= 105
# 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 minDiffInBST(self, root: TreeNode) -> int:
min_dist = 2**32-1
pre_node = -2**32-1
def inorder(root):
nonlocal pre_node, min_dist
if not root:
return
inorder(root.left)
min_dist = min(min_dist, root.val - pre_node)
pre_node = root.val
inorder(root.right)
inorder(root)
return min_distTips
和530是重复题
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] 输出：true
示例 2：
输入：root1 = [1], root2 = [1] 输出：true
示例 3：
输入：root1 = [1], root2 = [2] 输出：false
示例 4：
输入：root1 = [1,2], root2 = [2,2] 输出：true
示例 5：
输入：root1 = [1,2,3], root2 = [1,3,2] 输出：false
提示：
给定的两棵树可能会有 1 到 200 个结点。
给定的两棵树上的值介于 0 到 200 之间。
# 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 leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
ans = []
def get_leaves(root, ans):
if not root:
return
if not root.left and not root.right:
ans.append(root.val)
return ans
get_leaves(root.left, ans)
get_leaves(root.right, ans)
return ans
leaf1 = get_leaves(root1, [])
leaf2 = get_leaves(root2,[])
return leaf1==leaf2返回与给定的前序和后序遍历匹配的任何二叉树。
pre 和 post 遍历中的值是不同的正整数。
示例：
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
提示：
1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
# 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 constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
def dfs(pre, post):
if not pre:
return None
root = TreeNode(pre[0])
if len(pre)==1:
return root
L = post.index(pre[1])+1
root.left = dfs(pre[1:(L+1)], post[:L])
root.right = dfs(pre[(L+1):], post[L:-1])
return root
return dfs(preorder, postorder)Tips
前序遍历确认root，后序遍历确认左子树的节点数，因为左子树的root是pre[1]，也是post左子树的最后一个元素
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[2,1]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
提示：
树中节点数目在范围 [0, 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 inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res 迭代
中序遍历就是遍历左子树from bottom2top，打印root，遍历所有右子树from top2bottom。所以左子树入栈，右子树直接按顺序遍历即可
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = []
res = []
while stack or root:
while root:
stack.append(root)
root=root.left
root = stack.pop()
res.append(root.val)
root = root.right
return resTips
这题和144，145和在一起就是二叉树的前/中/后序遍历，前序中左右，中序是左中右，后序是左右中。分别用递归和迭代来解决
-
递归：递归三要素
- 停止条件：not root return
- 每一层的处理逻辑: 遍历左，加入当前val，遍历右
- 需要传入的参数和返回的变量： 传入当前node，直接用全局res来放node
-
迭代：把递归背后的实现逻辑用迭代直接实现一遍
-
中序遍历最常用于二叉搜索树的构建
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1：
输入：n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
输入：n = 1 输出：[[1]]
提示：
1 <= n <= 8
# 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 generateTrees(self, n: int) -> List[TreeNode]:
if n==0:
return []
cache = {}
def helper(start,end):
nonlocal cache
if (start,end) in cache:
return cache[(start,end)]
else:
nodes = []
if start>end:
cache[(start,end)] = [None]
return [None]
for root in range(start,end+1):
for left in helper(start, root-1):
for right in helper(root+1, end):
node = TreeNode(val=root)
node.left = left
node.right = right
nodes.append(node)
cache[(start,end)] = nodes
return nodes
trees = helper(1,n)
return trees Tips
- 可以类比简单版的构造balance 二叉搜索树，只不过这里需要遍历所有能构造的类型。依旧是前序遍历，root可以是start-end的任意一个值，左子树是start-root-1，右子树是root+1-end。因为在构造过程中会有重复的子树被构造，所以用cache来保留所有已经够熬过的子树（start,end)对应一个list的所有子树构造方式
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1] 输出：true
示例 2：
输入：[2,2,2,5,2] 输出：false
提示：
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。
# 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 isUnivalTree(self, root: TreeNode) -> bool:
val = root.val
def dfs(root):
if not root:
return True
return root.val == val and dfs(root.left) and dfs(root.right)
ans = dfs(root)
return ans给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3] 输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
- stack方案：中序遍历，搜索树满足left < root<right. 把所有左子树压入栈，然后从叶节点开始pop，每次pop都对比一次left,root,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 isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
cur = root
stack = []
pre = None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
if pre and cur.val<= pre.val:
return False
pre = cur
cur = cur.right
return True - 递归解法: 以下递归依旧是上面中序遍历的实现，只不过在中间加入cur_max也就是上一个节点的值进行判断即可
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
cur_max = -2**32
def helper(root):
if not root:
return True
left = helper(root.left)
if root.val <= cur_max:
return False
else:
cur_max = root.val
right = helper(root.right)
return left and right
return helper(root)给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 1：
输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1
# 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 recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
pre = None
node1 = None
node2 = None
def inorder(root):
nonlocal pre, node1, node2
if not root:
return
inorder(root.left)
if pre and pre.val > root.val:
if node1 is None:
node1 = pre
node2 = root
else:
node2= root
pre = root
inorder(root.right)
inorder(root)
node1.val, node2.val = node2.val, node1.valTips
- 依旧是二叉搜索树的中序遍历，因为有两个节点互换位置，先找到的一定是大node后找到的是小node。大node只用做一次判断即可，小node可能是和大node相邻，第一次就能找到，如果不相邻需要再找到下一个才是。