golang算法二叉樹對稱平衡右視圖

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.LeftinvertTree(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=rightroot.Right=leftreturn 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.Valleft:=mergeTrees(root1.Left,root2.Left)right:=mergeTrees(root1.Right,root2.Right)root1.Left=leftroot1.Right=rightreturn 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,falseif 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)intans:=[]int{}mp:=map[int]int{}max_len:=0dfs=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:=0dfs=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:=0dfs=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:=0dfs=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.Valif 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)intdfs=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
}