LeetCode 01/05/18

今天中午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;
}

今天有点晚了，刷不了十道题了，早点睡了明天多写几题来弥补吧。。。

LeetCode 01/05/18

推荐阅读更多精彩内容