100. 相同的树
给你两棵二叉树的根节点 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.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p==nil||q==nil{
return p==q
}
return p.Val==q.Val&&isSameTree(p.Left,q.Left)&&isSameTree(p.Right,q.Right)
}
101. 对称二叉树
给你一个二叉树的根节点 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.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isEqual(left *TreeNode,right *TreeNode)bool{
if left==nil||right==nil{
return left==right
}
return left.Val==right.Val&&isEqual(left.Left,right.Right)&&isEqual(left.Right,right.Left)
}
func isSymmetric(root *TreeNode) bool {
return isEqual(root.Left,root.Right)
}
110. 平衡二叉树
给定一个二叉树，判断它是否是 平衡二叉树
示例 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.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func abs(num int)int{
if num>0{
return num
}else{
return -1*num
}
}
func getHeight(node *TreeNode)int{
if node==nil{
return 0
}
left_height:=getHeight(node.Left)
if left_height==-1{
return -1
}
right_height:=getHeight(node.Right)
if right_height==-1 || abs(left_height-right_height)>1{
return -1
}
return max(left_height,right_height)+1
}
func isBalanced(root *TreeNode) bool {
return getHeight(root)!=-1
}
199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
ans:=[]int{}
var dfs func(root *TreeNode,depth int)
dfs=func(root *TreeNode,depth int){
if root==nil{
return
}
if depth==len(ans){
ans=append(ans,root.Val)
}
dfs(root.Right,depth+1)
dfs(root.Left,depth+1)
}
dfs(root,0)
return ans
}
965. 单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 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.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree2(root *TreeNode,target int)bool{
if root==nil{
return true
}
return root.Val==target&&isUnivalTree2(root.Left,target)&&isUnivalTree2(root.Right,target)
}
func isUnivalTree(root *TreeNode) bool {
if root==nil{
return true
}
return isUnivalTree2(root,root.Val)
}
951. 翻转等价二叉树
我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的函数，则返回 true ，否则返回 false 。
示例 1：
Flipped Trees Diagram
输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：我们翻转值为 1，3 以及 5 的三个节点。
示例 2:
输入: root1 = [], root2 = []
输出: true
示例 3:
输入: root1 = [], root2 = [1]
输出: false
提示：
每棵树节点数在 [0, 100] 范围内
每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
if root1==nil||root2==nil{
return root1==root2
}
return root1.Val==root2.Val&&((flipEquiv(root1.Left,root2.Right)&&flipEquiv(root1.Right,root2.Left))||(flipEquiv(root1.Left,root2.Left)&&flipEquiv(root1.Right,root2.Right)))
}
226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root==nil{
return nil
}
root.Left,root.Right=root.Right,root.Left
invertTree(root.Left)
invertTree(root.Right)
return root
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root==nil{
return nil
}
left:=invertTree(root.Left)
right:=invertTree(root.Right)
root.Left=right
root.Right=left
return root
}
617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
提示：
两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1==nil{
return root2
}
if root2==nil{
return root1
}
root1.Val+=root2.Val
left:=mergeTrees(root1.Left,root2.Left)
right:=mergeTrees(root1.Right,root2.Right)
root1.Left=left
root1.Right=right
return root1
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1==nil{
return root2
}
if root2==nil{
return root1
}
return &TreeNode{
root1.Val+root2.Val,
mergeTrees(root1.Left,root2.Left),
mergeTrees(root1.Right,root2.Right),
}
}
2331. 计算布尔二叉树的值
给你一棵 完整二叉树 的根，这棵树有以下特征：
叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
计算 一个节点的值方式如下：
如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。
否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。
完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点 是没有孩子的节点。
示例 1：
输入：root = [2,1,3,null,null,0,1]
输出：true
解释：上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ，所以我们返回 true 。
示例 2：
输入：root = [0]
输出：false
解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
提示：
树中节点数目在 [1, 1000] 之间。
0 <= Node.val <= 3
每个节点的孩子数为 0 或 2 。
叶子节点的值为 0 或 1 。
非叶子节点的值为 2 或 3 。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func detail(root *TreeNode)bool{
if root.Left==root.Right{
return root.Val==1
}
left,right:=false,false
if detail(root.Left){
left=true
}else{
left=false
}
if detail(root.Right){
right=true
}else{
right=false
}
if root.Val==2{
return left||right
}else{
return left&&right
}
}
func evaluateTree(root *TreeNode) bool {
if root==nil{
return false
}
return detail(root)
}
func evaluateTree(root *TreeNode) bool {
if root.Left == root.Right {
return root.Val == 1
}
if root.Val == 2 {
return evaluateTree(root.Left) || evaluateTree(root.Right)
}
return evaluateTree(root.Left) && evaluateTree(root.Right)
}
508. 出现次数最多的子树元素和
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
示例 1：
输入: root = [5,2,-3]
输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5]
输出: [2]
提示:
节点数在 [1, 104] 范围内
-105 <= Node.val <= 105
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findFrequentTreeSum(root *TreeNode) []int {
var dfs func(root *TreeNode)int
ans:=[]int{}
mp:=map[int]int{}
max_len:=0
dfs=func(root *TreeNode)int{
if root==nil{
return 0
}
if root.Left==root.Right{
mp[root.Val]++
if mp[root.Val]>max_len{
max_len=mp[root.Val]
}
return root.Val
}
tmp:=root.Val+dfs(root.Left)+dfs(root.Right)
mp[tmp]++
if mp[tmp]>max_len{
max_len=mp[tmp]
}
return tmp
}
dfs(root)
for k,v:=range mp{
if v==max_len{
ans=append(ans,k)
}
}
return ans
}
1026. 节点与其祖先之间的最大差值
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
示例 2：
输入：root = [1,null,2,null,0,3]
输出：3
提示：
树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 105
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func abs(num int)int{
if num>0{
return num
}else{
return -1*num
}
}
func maxAncestorDiff(root *TreeNode) int {
var dfs func(root *TreeNode,minNum int,maxNum int)
ans:=0
dfs=func(root *TreeNode,minNum int,maxNum int){
if root==nil{
return
}
if minNum>root.Val{
minNum=root.Val
}
if maxNum<root.Val{
maxNum=root.Val
}
if max(abs(minNum-root.Val),abs(maxNum-root.Val))>ans{
ans=max(abs(minNum-root.Val),abs(maxNum-root.Val))
}
dfs(root.Left,minNum,maxNum)
dfs(root.Right,minNum,maxNum)
}
dfs(root,root.Val,root.Val)
return ans
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxAncestorDiff(root *TreeNode) int {
var dfs func(root *TreeNode,mn int,mx int)
ans:=0
dfs=func(root *TreeNode,mn int,mx int){
if root==nil{
return
}
mn=min(mn,root.Val)
mx=max(mx,root.Val)
ans=max(ans,root.Val-mn,mx-root.Val)
dfs(root.Left,mn,mx)
dfs(root.Right,mn,mx)
}
dfs(root,root.Val,root.Val)
return ans
}
1372. 二叉树中的最长交错路径
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
示例 2：
输入：root = [1,1,1,null,1,null,null,1,1,null,1]
输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
示例 3：
输入：root = [1]
输出：0
提示：
每棵树最多有 50000 个节点。
每个节点的值在 [1, 100] 之间。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func longestZigZag(root *TreeNode) int {
if root==nil{
return 0
}else if root.Left==root.Right{
return 0
}
var dfs func(root *TreeNode,direction int,depth int)
maxDepth:=0
dfs=func(root *TreeNode,direction int,depth int){
if root==nil{
maxDepth=max(maxDepth,depth)
return
}
if direction==0{
dfs(root.Right,1-direction,depth+1)
dfs(root.Left,1-direction,-1)
}else{
dfs(root.Left,1-direction,depth+1)
dfs(root.Right,1-direction,-1)
}
}
dfs(root,0,-1)
dfs(root,1,-1)
return maxDepth
}
1080. 根到叶路径上的不足节点🪝
给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。
假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。
叶子节点，就是没有子节点的节点。
示例 1：
输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]
示例 2：
输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]
示例 3：
输入：root = [1,2,-3,-5,null,4,null], limit = -1
输出：[1,null,-3,4]
提示：
树中节点数目在范围 [1, 5000] 内
-105 <= Node.val <= 105
-109 <= limit <= 109
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
if root==nil{
return nil
}
limit-=root.Val
if root.Left==root.Right{
if limit>0{
return nil
}
return root
}
root.Left=sufficientSubset(root.Left,limit)
root.Right=sufficientSubset(root.Right,limit)
if root.Left==nil&&root.Right==nil{
return nil
}
return root
}
还得想想怎么修改
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
var dfs func(root *TreeNode,sum int)int
dfs=func(root *TreeNode,sum int)int{
if root==nil{
return 0
}
if root.Left==root.Right{
return root.Val+sum
}
result:=max(dfs(root.Left,sum+root.Val),dfs(root.Right,sum+root.Val))
if result<limit{
root=nil
}
return result
}
dfs(root,0)
return root
}