二叉樹

• NC72 二叉樹的鏡像 （前序遍歷交換左右子樹+遞歸）
• leetcode 116. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針 （借助輔助函數(shù)傳入兩個結(jié)點）
• leetcode114. 二叉樹展開為鏈表 （后序遍歷，左子樹移到右子樹，原來的右子樹接到新的右子樹后）
• leetcode 654. 最大二叉樹 （前序遍歷找出最大值作為根結(jié)點+遞歸）
• leetcode 105. 從前序與中序遍歷序列構(gòu)造二叉樹 （前序遍歷，先找根結(jié)點位置，再遞歸）
• leetcode 222. 完全二叉樹的節(jié)點個數(shù) (后序遍歷，節(jié)點個數(shù)=左子樹+右子樹+1)
• leetcode 652. 尋找重復(fù)的子樹 （每棵子樹轉(zhuǎn)為字符串，用一個hashmap存子樹出現(xiàn)次數(shù)，linkedlist存重復(fù)子樹根結(jié)點）
• NC13 二叉樹的最大深度（后序遍歷）
• leetcode 102. 二叉樹的層序遍歷（用隊列存一層結(jié)點）
• NC8 二叉樹中和為某一值的路徑(二) （dfs，用path記錄當(dāng)前的路徑）
• NC81 二叉搜索樹的第k個節(jié)點（二叉搜索樹中序遍歷剛好是升序結(jié)果）
• leetcode538. 把二叉搜索樹轉(zhuǎn)換為累加樹（改變中序遍歷的遞歸順序可以得到降序輸出 右-根-左）
• leetcode 98. 驗證二叉搜索樹（輸出中序遍歷結(jié)果，判斷是否符合升序）
• leetcode 101. 對稱二叉樹 （借助輔助函數(shù)，傳入兩個結(jié)點進(jìn)行遞歸）
• NC62 判斷是不是平衡二叉樹 （遞歸計算每個結(jié)點的高度，并計算左右子樹的高度差，用bool記錄是否平衡）
• NC11 將升序數(shù)組轉(zhuǎn)化為平衡二叉搜索樹（二分法找中間元素作為根結(jié)點再遞歸左右子樹）
• NC9 二叉樹中和為某一值的路徑(一) （前序遍歷）
• NC60 判斷一棵二叉樹是否為搜索二叉樹和完全二叉樹 （搜索二叉樹：中序遍歷后得到的是升序，完全二叉樹：層序遍歷，遇到不同時擁有左右兒子的結(jié)點以后，出隊的所有結(jié)點都是葉結(jié)點。且不會出現(xiàn)只有右兒子的結(jié)點）
• NC136 輸出二叉樹的右視圖（）
• NC117 合并二叉樹 （把第二棵樹每個結(jié)點上的值加到第一棵樹，base case是兩棵樹中存在空節(jié)點時）
• NC6 二叉樹中的最大路徑和（后序遍歷，遞歸計算最大貢獻(xiàn)值，再計算最大路徑和）
• NC14 按之字形順序打印二叉樹（層序遍歷+判斷奇偶層）
• NC5 二叉樹根節(jié)點到葉子節(jié)點的所有路徑和 （sum=presum*10+root.val）

遞歸

• NC26 括號生成（遞歸，記錄左括號和右括號剩余的個數(shù)）

棧

• 有效括號序列（左括號入棧，右括號出棧）

DFS

• 島嶼數(shù)量（dfs，發(fā)現(xiàn)島嶼就把相鄰島嶼都淹沒，島嶼數(shù)+1）

動態(tài)規(guī)劃

• NC126 兌換零錢(一)
• NC7 買賣股票的最好時機(一) （第i天是否賣出）
• NC163 最長上升子序列(一) （dp[i]定義為以arr[i]為結(jié)尾，最長上升子序列的長度）
• NC165 最長公共子序列(一) （二維dp）
• NC92最長公共子序列(二) （利用上一題生成好的dp倒退回去）
• NC153 信封嵌套問題 （對w升序，w相同則h降序，再對h進(jìn)行NC163的操作）
• NC19 連續(xù)子數(shù)組的最大和（dp[i]定義為以array[0]為結(jié)尾的連續(xù)子數(shù)組）
• NC154 最長回文子序列（二維dp）

總結(jié)

以上是生活随笔為你收集整理的12月刷题记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。