泛型遞歸、樹的遞歸
視訊教程：B站、網易雲課堂、騰訊課堂
代碼位址：Gitee、Github
存儲位址：
百度雲-提取碼：
Google雲
- 1.爬樓梯
- 2.括号生成
- 3.翻轉二叉樹
- 4.驗證二叉搜尋樹
- 5.二叉樹的最大深度
- 6.二叉樹的最小深度
- 7.二叉樹的序列化與反序列化
- 8.二叉樹的最近公共祖先
- 9.從前序與中序周遊序列構造二叉樹
- 10.組合
- 11.全排列
- 12.全排列 II
- 爬樓梯
國内站
java版
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
python版：
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
c++版：
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
國外站
/*
思路：
*/
class Solution {
public int climbStairs(int n) {
if(n <= 0) return 0;
if(n ==1 ) return 1;
if(n ==2 ) return 2;
int one_step_before = 2;
int two_steps_before = 1;
int all_ways = 0;
for (int i = 2;i<n;i++) {
all_ways = one_step_before +two_steps_before;
two_steps_before = one_step_before;
one_step_before = all_ways;
}
return all_ways;
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 括号生成
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
The idea here is to only add ‘(’ and ‘)’ that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a ‘(’ we will then discard it and try a ‘)’ which can only close a valid ‘(’. Each of these steps are recursively called.
/*
思路：
*/
class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
backtrack(list, "", 0, 0, n);
return list;
}
public void backtrack(List<String> list, String str, int open, int close, int max){
if(str.length() == max*2){
list.add(str);
return;
}
if(open < max)
backtrack(list, str+"(", open+1, close, max);
if(close < open)
backtrack(list, str+")", open, close+1, max);
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 翻轉二叉樹
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 驗證二叉搜尋樹
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
if (root == null) return true;
if (root.val >= maxVal || root.val <= minVal) return false;
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 二叉樹的最大深度
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 二叉樹的最小深度
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 二叉樹的序列化與反序列化
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
The idea is simple: print the tree in pre-order traversal and use “X” to denote null node and split node with “,”. We can use a StringBuilder for building the string on the fly. For deserializing, we use a Queue to store the pre-order traversal and since we have “X” as null node, we know exactly how to where to end building subtress.
/*
思路：
*/
public class Codec {
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}
private void buildString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
} else {
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}
private TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(NN)) return null;
else {
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 二叉樹的最近公共祖先
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left != null ? left : right;
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 從前序與中序周遊序列構造二叉樹
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
The basic idea is here:
Say we have 2 arrays, PRE and IN.
Preorder traversing implies that PRE[0] is the root node.
Then we can find this PRE[0] in IN, say it’s IN[5].
Now we know that IN[5] is root, so we know that IN[0] - IN[4] is on the left side, IN[6] to the end is on the right side.
Recursively doing this on subarrays, we can build a tree out of it ????
/*
思路：
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 組合
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
class Solution {
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combs = new ArrayList<List<Integer>>();
combine(combs, new ArrayList<Integer>(), 1, n, k);
return combs;
}
public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
if(k==0) {
combs.add(new ArrayList<Integer>(comb));
return;
}
for(int i=start;i<=n;i++) {
comb.add(i);
combine(combs, comb, i+1, n, k-1);
comb.remove(comb.size()-1);
}
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 全排列
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
- 全排列 II
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
/*
思路：
*/
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
dfs(nums, used, list, res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
used[i]=true;
list.add(nums[i]);
dfs(nums,used,list,res);
used[i]=false;
list.remove(list.size()-1);
}
}
}
/*
評價：
優點：
缺點：
*/
'''
思路：
'''
'''
評價：
優點：
缺點：
'''
/*
思路：
*/
/*
評價：
優點：
缺點：
*/
一 遞歸的實作、特性以及思維要點
二 實戰題目解析：爬樓梯、括号生成等問題