前言

問問自己，刷題的效果真的達到了嗎？

內容

一、翻轉二叉樹

226.翻轉二叉樹

給你一棵二叉樹的根節點?root?，翻轉這棵二叉樹，并返回其根節點。

遞歸

func invertTree(root *TreeNode) *TreeNode {if root==nil{return root}root.Left,root.Right=root.Right,root.LeftinvertTree(root.Left)invertTree(root.Right)return root
}

二、對稱二叉樹

101.對稱二叉樹

給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。

遞歸

我們可以實現這樣一個遞歸函數，通過「同步移動」兩個指針的方法來遍歷這棵樹，p 指針和 q 指針一開始都指向這棵樹的根，隨后 p 右移時，q 左移，p 左移時，q 右移。每次檢查當前 p 和 q 節點的值是否相等，如果相等再判斷左右子樹是否對稱。

func isSymmetric(root *TreeNode) bool {return  dfs(root.Left,root.Right)}func dfs(left *TreeNode,right *TreeNode) bool{if left==nil&&right==nil{return true}if left==nil||right==nil{return false}if left.Val!=right.Val{return false}return dfs(left.Left,right.Right)&&dfs(left.Right,right.Left)
}

迭代?

把遞歸程序改寫成迭代程序

func isSymmetric(root *TreeNode)bool{u,v:=root,rootqueue:=[]*TreeNode{}queue=append(queue,u)queue=append(queue,v)for len(queue)>0{u,v = queue[0],queue[1]queue=queue[2:]if u==nil&&v==nil{//要先判斷continue}if u==nil||v==nil{return false}if u.Val!=v.Val{return false}queue=append(queue,u.Left)queue=append(queue,v.Right)queue=append(queue,u.Right)queue=append(queue,v.Left)}return true
}

三、完全二叉樹的節點個數

222.完全二叉樹的節點個數

給你一棵?完全二叉樹?的根節點?root?，求出該樹的節點個數。

完全二叉樹?的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第?h?層，則該層包含?1~?2h?個節點。

廣度優先搜素

func countNodes(root *TreeNode) int {var count intif root==nil{//沒有這個會報錯 昨天遇到過return 0}level:=[]*TreeNode{root}for len(level)>0{temp:=levellevel=nilfor _,node:=range temp{count++if node.Left!=nil{level=append(level,node.Left)}if node.Right!=nil{level=append(level,node.Right)}}}return count
}

最后

令人心動的offer啊，能拿到嗎？