今天中午suki点了小米椒鸡丁，很好吃，起得一如既往地晚，起床玩了会儿就吃饭了，好吧，赶紧滚去刷题了。。
- Binary Tree Inorder Traversal
Inorder 用法
I will show you all how to tackle various tree questions using iterative inorder traversal. First one is the standard iterative inorder traversal using stack.
Question : Binary Tree Inorder Traversal
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
Now, we can use this structure to find the Kth smallest element in BST.
- Kth Smallest Element in a BST
Question : Kth Smallest Element in a BST
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
We can also use this structure to solve BST validation question.
- Validate Binary Search Tree
Question : Validate Binary Search Tree
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}
- Invert Binary Tree
recursive way
TreeNode left = root.left;
TreeNode right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
iterative way
use stack 不太理解
Diameter of Binary Tree
此题与110. Balanced Binary Tree相似， 两次递归
一次求height 一次遍历整个🌲Sum of Left Leaves
if (cur.left != null) {
if (cur.left.left == null && cur.left.right == null) {
sum += cur.left.val;
} else {
sum += sumOfLeftLeaves(cur.left);
}
}
sum += sumOfLeftLeaves(cur.right);
- Swap Nodes in Pairs
reverse变种 定义四个node prev，cur， next， nextNext
睡前跟孔神来了个mock interview， 感觉自己被爆成渣，而且因为第一次mock， 很紧张脑子里很容易乱，好在后来在提醒下还算是写出来了
题目是扁化多层链表
public Node flatList(Node head) {
if (head == null) {
return null;
}
Queue<Node> que = new LinkedList<>();
Node cur = head;
if (cur.child != null) {
cur = cur.next;
} else {
que.offer(cur);
}
while (!que.isEmpty()) {
while (cur != null) {
if (cur.child != null) {
que.offer(cur);
cur = cur.next;
}
}
cur.next = que.poll();
}
return head;
}
public Node flatList(Node head) {
if (head == null) {
return null;
}
Queue<Node> que = new LinkedList<>();
Node stub = new Node();
que.offer(head);
while(!que.isEmpty()) {
Node curr = que.poll();
stub.next = curr;
while(curr != null) {
Stub = curr;
if(curr.child != null) {
que.offer(curr.child);
}
curr = curr.next;
}
}
Return head;
}
Node{
Int key;
Node next;
Node child;
}
今天有点晚了，刷不了十道题了，早点睡了明天多写几题来弥补吧。。。
