遞歸代碼模板

# Python def recursion(level, param1, param2, ...): # recursion terminator 終止條件判斷if level > MAX_LEVEL: # process_result return # process logic in current level 當前遞歸邏輯處理process(level, data...) # drill down 遞歸調用self.recursion(level + 1, p1, ...) # reverse the current level status if needed 處理一些狀態

實戰題目
爬樓梯
括號問題22
二叉樹翻轉226
二叉搜索樹校驗98 搜索樹是不允許相等的元素存在的
二叉樹最大深度104
二叉樹最小深度111
二叉樹的序列化反序列化297
每日一課
如何優雅地計算斐波那契數列

課后作業
二叉樹兩個節點的公共祖先236
前序遍歷與中序遍歷構造二叉樹105
n個數中所有可能結合77
沒有重復 數字的序列，返回其所有可能的全排列46
可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列47

小結 01

一天做了10個左右的題，頭暈腦脹，感覺相似的題目卻又不同，所以有些題目做的很費勁，沒有很好的處理，做完了效果也不是很好，并不像之前做完一個，都會有一些思路去處理，一些注意事項等等，現在感覺做完了就全憑感覺的樣子，還需要冷靜思考總結才行。
而且，雖然知道了這些題目都是針對遞歸的訓練題目，但是并不是僅僅這樣就夠了，還需要注意的是有些題目是比較復雜的，是有邏輯需要抽象處理的，并不是知道用遞歸就行了，還要注意問題處理的過程，邊界等。比如括號的問題，還是要了解有效括號的特性，知道如何迭代才行。
什么是有效的二叉搜索樹，二叉搜索樹的中序遍歷特點是否可以用上等，有很多都是需要畫圖才能夠真正解決的。但是這里條件有限，所以也別太心急，多做幾遍就好了，加油。每個題都去思考對應的邏輯，處理邏輯，而不是總想一次帶走，有些需要更多的邏輯處理來支撐，分析問題，找到問題的核心邏輯，找到重復點，才有助于解決問題。

同時，通過對下面的二叉樹公共祖先的學習，進一步認識到了
狀態空間和結果空間的區別
狀態空間，是指問題本身可能有哪些情況，比如下面的分析
結果空間則是問題通過當前的解答方式可以得到的答案有哪些，比如括號組合的題，最后需要在解空間中進行過濾，得到全部合法的解，還有就是最大矩形面積，如果按照每個bar的高作為矩形的高進行枚舉，則也是構建了一個解空間，在這個解空間中最終搜索只會得到一個最優解

有些問題需要對狀態空間更好的劃分，才更好得到解空間
而有些問題則不是構建解空間，而是直接求解得到唯一解，并不涉及最優概念，而是一個對錯型的題，只有一個解，比如矩形面積，是多個解找最大的（數據線構建解空間再求解的情況），共同父節點則是直接得到最終解（沒有解空間的概念）

小結02 二叉樹兩個節點的公共祖先

/*** 這個問題的分析，從網上看的思路，感覺有些很好，這里應該怎樣分析* 首先是問題的狀態空間* 1. 兩個節點是父子關系* 1. 找到的時候肯定是先找到parent，直接返回parent即可** 2. 兩個節點不是父子關系* 在某個子樹中沒有找到，只需要返回null** 1. 在某個節點的左子樹和右子樹中都找到了，說明當前節點為target,逐層返回之** 2. 在某個節點的其中一個子樹中找到某一個節點（或則兩個），返回chiled返回的節點，即代表找到了至少一個節點，* 如果在其他層級的遍歷中無法找到節點，則說明這個子樹中有兩個這個節點，這個返回的非null糅合了多種情況，隱含了樹中必然有兩個節點的條件****/

可以得到這個精簡的代碼

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == p || root == q || root == null){return root;}TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if((left != null)&&(right != null)){return root;}if (left != null) {return left;} else {return right;}}

小結03 可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列47

非常開心，這個題通過自己的探索得到了一個新的解法，而且效率也算中規中矩，60%以上
這個是根據不重復的全排推出來的，在每個迭代中增加了一個map，如果有重復的就不交換位置了

class Solution {List<List<Integer>> res = new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {List<Integer> numList = new LinkedList<>();for (int i : nums) {numList.add(i);}unique(numList, 0, nums.length);return res;}private void unique(List<Integer> numList, int cur, int len) {if (cur == len - 1) {res.add(new ArrayList<>(numList));return;}// 這里增加了一個map用來判斷，就是沒法重復用，有點可惜Map<Integer, Boolean> dic = new HashMap<>();for (int i = cur; i < len; i++) {if (dic.get(numList.get(i)) != null) {continue;}Collections.swap(numList, i, cur);unique(numList, cur + 1, len);Collections.swap(numList, i, cur);dic.put(numList.get(i), Boolean.TRUE);}}}

更好的答案應該是體統了更好的時間復雜度，節約了不少時間,但是思路不太一樣

class Solution {boolean[] vis;public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> perm = new ArrayList<Integer>();vis = new boolean[nums.length];Arrays.sort(nums);backtrack(nums, ans, 0, perm);return ans;}public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {if (idx == nums.length) {ans.add(new ArrayList<Integer>(perm));return;}for (int i = 0; i < nums.length; ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}perm.add(nums[i]);vis[i] = true;backtrack(nums, ans, idx + 1, perm);vis[i] = false;perm.remove(idx);}} }

總結

以上是生活随笔為你收集整理的算法训练营07-递归使用练习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。