題目匯總

以下鏈接均為我博客內對應博文，有解題思路和代碼，不定時更新補充。

目前范圍：Leetcode前150題

生成二叉樹

• Construct Binary Tree from Preorder and Inorder Traversal (Inorder and Postorder)
  根據(jù)二叉樹的前序遍歷和中序遍歷（中序和后序）結果生成二叉樹
  遞歸

• Convert Sorted Array to Binary Search Tree
  將一個排序好的數(shù)組轉換為一顆二叉查找樹，這顆二叉查找樹要求是平衡的。
  Convert Sorted List to Binary Search Tree
  將一個排序好的鏈表轉換為一顆二叉查找樹，這顆二叉查找樹要求是平衡的。
  遞歸

• Unique Binary Search Trees
  給定一個數(shù)n，求1-n這n個數(shù)能生成多少個二叉查找樹
  動態(tài)規(guī)劃
  卡特蘭數(shù)（組合數(shù)學）

• Unique Binary Search Trees II
  給出一個n，求1-n能夠得到的所有二叉搜索樹，輸出所有樹
  遞歸
  較難

遍歷二叉樹

• Binary Tree Preorder Traversal
  前序遍歷一個二叉樹
  遞歸、迭代

• Binary Tree Inorder Traversal
  中序遍歷一個二叉樹
  遞歸、迭代

• Binary Tree Inorder Traversal
  后序遍歷一個二叉樹
  遞歸、迭代

前中后三種序列，遞歸都是一樣的理解。迭代的話，前后兩個可以互相理解。中序需要單獨理解。當然我認為可能我還沒有理解透徹。

• Binary Tree Level Order Traversal
  層序遍歷，每一層上的數(shù)據(jù)按照從左到右的順序排列。
  遞歸、迭代

• Binary Tree Level Order Traversal II
  層序遍歷，這次是從最下層輸出到根節(jié)點
  遞歸、迭代

• Binary Tree Zigzag Level Order Traversal
  按之字形遍歷二叉樹（一正一反）
  遞歸、迭代

這三題都是層序遍歷，沒有什么特別大的區(qū)別。層序遍歷基本都這樣，舉一反三。

• Path Sum
  給定一個數(shù)和一棵樹，求能否有一條路徑上所有葉子結點數(shù)值加起來等于給定的數(shù)
  遞歸

• Path Sum II
  將根到葉子的路徑和為sum的路徑都枚舉出來。
  遞歸

第二題只不過是第一題得所有可能性保存到一個數(shù)組去。

其他題目

• Maximum Depth of Binary Tree
  求二叉樹最大深度
  遞歸 DFS

• Minimum Depth of Binary Tree
  求二叉樹最小深度
  遞歸 DFS

• Validate Binary Search Tree
  判斷一棵樹是否為二叉搜索樹
  遞歸

• Recover Binary Search Tree
  一顆二叉查找樹中的某兩個節(jié)點被錯誤的交換了，需要恢復成原來的正確的二叉查找樹。
  遞歸

• Same Tree
  判斷兩顆二叉樹是否完全相同
  遞歸

• Symmetric Tree
  判斷一個樹是否左右對稱
  遞歸、迭代

上面兩題類似

• Balanced Binary Tree
  判斷一顆二叉樹是否是“高度”平衡的。
  平衡二叉樹的定義是二叉樹的任意節(jié)點的兩顆子樹之間的高度差小于等于1。
  遞歸

• Flatten Binary Tree to Linked List 難題
  把一棵二叉樹變?yōu)殒湵恚ū馄交?br> 迭代

• Sum Root to Leaf Numbers
  要求所有從根節(jié)點到葉子節(jié)點組成的數(shù)字的和。
  遞歸

• Binary Tree Maximum Path Sum
  求一棵二叉樹中最大的路徑和。
  遞歸

• Populating Next Right Pointers in Each Node I and II
  為二叉樹的節(jié)點都添加一個next指針，指向跟它在同一高度的右邊的節(jié)點，如果右邊沒有節(jié)點，就指向None。
  迭代、遞歸

二叉樹總結

• leetcode的測試集經(jīng)常會有[], [0]，所以很多題目先要考慮判斷是否為空，return None或者return []。

• 遞歸和迭代
  遞歸中必有迭代，迭代未必用到遞歸
  （遞歸（浪費資源反復調用函數(shù)）> 迭代）
  迭代——《明日邊緣》
  遞歸——《盜夢空間》
  遞歸是一個樹結構，每個分支都探究到最遠，發(fā)現(xiàn)無法繼續(xù)的時候往回走，每個節(jié)點只會訪問一次
  迭代是一個環(huán)結構，每次迭代都是一個圈，不會拉掉其中的某一步，然后不斷循環(huán)，每個節(jié)點都會被循環(huán)訪問

• 二叉樹在python中用法
  root.val是該節(jié)點的值。
  root則相當于指向該節(jié)點的指針。
  root.left, root.right指向其左右節(jié)點的位置