为什么要先刷二叉树呢?
刷二叉树时看到题目没思路?
1void traverse(TreeNode root) {
2 // 前序遍历
3 traverse(root.left);
4 // 中序遍历
5 traverse(root.right);
6 // 后序遍历
7}
1int ans = INT_MIN;
2int oneSideMax(TreeNode* root) {
3 if (root == nullptr) return 0;
4
5 int left = max(0, oneSideMax(root->left));
6 int right = max(0, oneSideMax(root->right));
7
8 /**** 后序遍历 ****/
9 ans = max(ans, left + right + root->val);
10 return max(left, right) + root->val;
11 /****************/
12}
1TreeNode buildTree(int[] preorder, int preStart, int preEnd,
2 int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
3
4 if(preStart > preEnd || inStart > inEnd) return null;
5
6 /**** 前序遍历 ****/
7 TreeNode root = new TreeNode(preorder[preStart]);
8 int inRoot = inMap.get(root.val);
9 int numsLeft = inRoot - inStart;
10 /****************/
11
12 root.left = buildTree(preorder, preStart + 1, preStart + numsLeft,
13 inorder, inStart, inRoot - 1, inMap);
14 root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
15 inorder, inRoot + 1, inEnd, inMap);
16 return root;
17}
1void traverse(TreeNode* node) {
2 if (!node) return;
3
4 traverse(node->left);
5
6 /****中序遍历 ****/
7 if (node->val < prev->val) {
8 s = (s == NULL) ? prev : s;
9 t = node;
10 }
11 prev = node;
12 /****************/
13
14 traverse(node->right);
15}
1def coinChange(coins: List[int], amount: int):
2
3 def dp(n):
4 if n == 0: return 0
5 if n < 0: return -1
6
7 res = float('INF')
8 for coin in coins:
9 subproblem = dp(n - coin)
10 # 子问题无解,跳过
11 if subproblem == -1: continue
12 res = min(res, 1 + subproblem)
13 return res if res != float('INF') else -1
14
15 return dp(amount)
1def dp(n):
2 for coin in coins:
3 dp(n - coin)
1void backtrack(int[] nums, LinkedList<Integer> track) {
2 if (track.size() == nums.length) {
3 res.add(new LinkedList(track));
4 return;
5 }
6
7 for (int i = 0; i < nums.length; i++) {
8 if (track.contains(nums[i]))
9 continue;
10 track.add(nums[i]);
11 // 进入下一层决策树
12 backtrack(nums, track);
13 track.removeLast();
14 }
15
16/* 提取 N叉树遍历框架 */
17void backtrack(int[] nums, LinkedList<Integer> track) {
18 for (int i = 0; i < nums.length; i++) {
19 backtrack(nums, track);
20}
付东来(@labuladong) 著
GitHub 68.8k star的硬核算法教程
labuladong带你挑战力扣算法题
本书专攻算法刷题,训练算法思维,应对算法笔试。注重用套路和框架思维解决问题,以不变应万变。
(扫码了解本书详情)