【第三轮】7.7-7.13 CareerCup 4.6

【解题思路】1. if the node has a right child, return the leftmost node of its right subtree
2. else if the node is the left child of its parent, return its parent
3. else (the node is the right child of its parent) then keep searching upwards the tree until the situation of (2) is found
【时间复杂度】o(n)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/b5f7b62a0ae43c9a98f1

【解题思路】
two cases:
1.  node has a right child.  Then the next node is the most left node of its right subtree;
2.  node has no right child.  Then we need to find the first ancestor that is the left child of its own parent.  then the parent is exactly the node we need.  If we reach root before find the needed node, we should return null which means there is no next node.
【时间复杂度】 O(H)
【空间复杂度】 O(1)
【gist link】 https://gist.github.com/jyhjuzi/5d88cc27d9b91c763dcb

【解题思路】
  case1: nood.right == null : traverse to father untile node != node.father.right
  case2: nood.right != null: traverse to right, and find the minimum
其实不用father指针更好做，从root往下找，key小了就记下指针往左，key大了就往右走

【时间复杂度】 O(H)
【空间复杂度】 O(1)
【gist link】
https://gist.github.com/Noahsark/7124940b34eccc34a31a

【解题思路】
1.  node has a right child.  Then the next node is the most left node of its right subtree;
2.  node has no right child && node <= its parent, next node = parent
2.  node has no right child && node > its parent, keep search for parent of parent until find, else return NULL
【时间复杂度】 O(logn)
【空间复杂度】 O(1)
【gist link】https://gist.github.com/xun-gong/f4497902c29bc0c1cdf5