youxiwang

题解

/ 注册

全部文章 / 题解（共5篇）

题解 | JAVA 分治 #重建二叉树# [P0]

递归, 分治跟精华解法一样思路，通过preOrder找root，inOrder找左右subtree的size. 唯一不一样的就是用HashMap存inOrder的[val -> index]。这样跑起来快很多。时间 O(n): 每个node都会call一次build() 空间 O(n):...

Java 分治递归二叉树

2022-01-21

1 475

题解 | JAVA #将升序数组转化为平衡二叉搜索树# [P0]

递归，分治有序数组选中间点m作为root，recursiely build subtrees m.left = build [l, m) m.right = build [m+1, r) public class Solution { public TreeNode sortedArra...

Java 二叉树分治递归

2022-01-21

0 322

题解 | JAVA DFS#二叉树根节点到叶子节点的所有路径和# [P0-T2]

DFS DFS时传递parentSum, childSum = parentSum*10 + child.val 时间O(n): 每个node访问一次空间O(n): 因为是recursion，worst-case树是长条所有node都在栈上 public class Solution { ...

Java 二叉树

2022-01-21

1 379

题解 Java DFS recurse| #在二叉树中找到两个节点的最近公共祖先 [P1]

用一个global var记录LCA，然后dfs返回subtree里一共找到几个target。如果两个都找到了 skip之后所有的backtrack(这个解法关键在于要确保LAC只被set一次) time O(n), space O(h), where h is height of tree. ...

Java 二叉树

2022-01-09

1 282

题解 JAVA Deque | #按之字形顺序打印二叉树# [P1]

正常level-order traversal(因为比较好理解). 在visit的时候，用Deque去存值(因为Deque既是Queue也是Stack)。如果正向就当Queue(i.e. offer), 反向就当stack(i.e. push)。最后用Collection的copy construc...

Java 二叉树链表堆(优先队列)

2022-01-09

3 407