173. Binary Search Tree Iterator
每次做到这道题都忘记怎么做。用一个栈来保存。
在这边用了DFS inorder 的顺序保存的数据。
void DFS(TreeNode node){ if(node.left == null && node.right == null) { stack.push(node); return; } if(node.right != null) DFS(node.right); stack.push(node); if(node.left != null) DFS(node.left); return; } - 要学习的点：
标准答案里是采用的另一种inorder 的变形，首先所有的left side node push进去，然后每pop出一个节点，把它的right node push进去，再把right node 的 left side node push进去。
public class BSTIterator { private Stack stack = new Stack (); public BSTIterator(TreeNode root) { pushAll(root); } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stack.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode tmpNode = stack.pop(); pushAll(tmpNode.right); return tmpNode.val; } private void pushAll(TreeNode node) { for (; node != null; stack.push(node), node = node.left); }} 96. Unique Binary Search Tree
G(n) 代表的是n个节点有多少个unique bst
F(i, n)代表的是当i做root的时候，有多少个bst。F(i, n) = G(i-1) * G(n-i)
public int numTrees(int n){ int[] G = int[n+1]; for(int i =1; i <= n; ++i){ for(int j = 1; j <= I; ++j){ G[i] += G[j-1]*G[i-j]; } } return G[n];}
235. Lowest Common Ancestor of a BST
_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5
考虑三种情况： 1 节点均在root的左边或者右边，向左／右查找
2 节点一个在root的左边，一个在右边-》 root为LCA
3 节点之一即是root root为LCA
- recursion
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if((p.val - root.val)*(q.val - root.val) <= 0) return root; return p.val>root.val ? lowestCommonAncestor(root.right,p,q):lowestCommonAncestor(root.left,p,q); }}
- iteration
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while((p.val - root.val)*(q.val - root.val) > 1){ root = p.val - root.val > 0 ? root.right:root.left; } return root; }}
236. Lowest Common Ancestor of a BT
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4
对左右两边，进行寻找，只要找到q，p node就return此node。 如果左右两边都找到node，则证明这两个node分别在左右两个分支上，则当前root就是LCA。如果只有一边找到说明，找到的那个就是root。
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || p == root || q == root) return root; TreeNode nl = lowestCommonAncestor(root.left, p, q); TreeNode nr = lowestCommonAncestor(root.right, p, q); if(nl != null && nr != null){ return root; }else if(nl == null && nr == null){ return null; }else{ return nl == null ? nr:nl; } }}
116. Populating Next Right Poniters in Each Node
竟然一遍AC了哈哈哈哈哈开心，但是实现还是比别人的复杂了不少。
- 我的方法：用两个Queue来存node.
public class Solution { public void connect(TreeLinkNode root) { Queue q1 = new LinkedList (); Queue q2 = new LinkedList (); q1.add(root); while(q1.peek() != null || q2.peek() != null){ if(q1.peek() != null){ TreeLinkNode n1 = q1.poll(); while(n1 != null){ q2.add(n1.left); q2.add(n1.right); TreeLinkNode n2 = q1.poll(); n1.next = n2; n1 = n2; } } if(q2.peek() != null){ TreeLinkNode n1 = q2.poll(); while(n1 != null){ q1.add(n1.left); q1.add(n1.right); TreeLinkNode n2 = q2.poll(); n1.next = n2; n1 = n2; } } } }} - iteration solution
start-level 负责控制纵向的向下延伸，cur 负责横向的延伸。
-
public class Solution { public void connect(TreeLinkNode root) { TreeLinkNode start_level = root; while(start_level != null){ TreeLinkNode cur = start_level; while(cur != null){ if(cur.left != null) cur.left.next = cur.right; if(cur.right != null && cur.next != null) cur.right.next = cur.next.left; cur = cur.next; } start_level = start_level.left; } }} - recursion solution
public class Solution { public void connect(TreeLinkNode root) { if(root == null) return; if(root.left != null){ root.left.next = root.right; if(root.next != null) root.right.next = root.next.left; } connect(root.left); connect(root.right); }} 注意：一定要把对root.next != null 的判断放在里面，因为做到最下面一层，叶子可以有next但是没有left和right。