Recursion

Date: April 21, 2023

Topic: Recursion

Recall

Recursion 与 1D or 2D Array结合

1.1 8 x 8 queen

Recursion 与Linked List结合

pair by pair

reverse a binary tree upside down

recursion与Tree结合

LAC

Notes

• 2D array

• 逐层递归

• High level：找到所有摆放的可能：DFS

• Base case

• Recursive rule：

• 同一行：因为每行放一个，所以行不需要额外的check

• 同一列：遍历前面的每个点，check他们的col和我的candidate的col是否相同

• 同一对角线：遍历前面的每个点，check他们和candidate斜率的绝对值==1

• TC: node的个数： O(n!), 每个点做valid check： O(n) O(n! * n)

• SC: call stack角度→ O(n), heap: O(h)

• base case: head == null || head.next == null → return head

• 当前层需要做哪些事

• 1

• 2

• way of thinking (Tricks)

• what do you expect from your lchild/ rchild?

• what do you want to do in the current layer?

• what do you want to report to your parent?

• Assumption：a和b都在tree里

• 遇见a

• a and b 非直接互相隶属关系

• tips：

• 当前找到a/b的话，a和b的lca有可能在a/ b的下面吗：找到a/b就可以自然返回a/ b

• 如果一个左边返回的有东西，右边返回的有东西，这个点自己就是LCA

• 全局只有一个点会出现左边不是null，右边不是null的情况，这个点就是LCA

• base case：root == null || root == a || root == b →return root

• general case

<aside> 📌 SUMMARY:

</aside>

Date: May 15, 2023

Topic: Recursion 小灶

Recall

如何理解tree问题三部曲Recursion和DFS的区别

Q1:Binary Tree Path

Notes

DFS问题的两个解法，回答两个问题

• 每层代表什么意义？一般来讲解体之前就知道DFS要recurse多少层
• 每层有多少个状态需要try
• 这两个问题的含义？
• Recursion Tree代表什么物理意义？
• 如何画出recursion Tree

DFS和recursion的区别是构建解的顺序不一样

Step 1: Function能做什么

List<String> binaryTreePaths(TreeNode root)给我一个root节点，我能返回所有从root出发到各个leaf node path

Step 2: Base case

root == null, return empty list

root is leaf, return list of itself

Step 3: subproblem

root.left

root.right

Step 4: Recursion rule

Difference between Recursion and DFS

• recursion构建解的顺序是自下而上的
• Method DFS（自上而下的构建Solution）

<aside> 📌 SUMMARY:

</aside>

Date: May 15, 2023

Topic: Recursion III

Recall

Q1. Tree + Recursion 第一类问题

Summary of tree path description

path problem in binary tree

<aside> 📌 SUMMARY:

</aside>