czxttkl

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Code

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None: 
            return
        
        pre = root
        while pre.left:
            pre_bakup = pre

            while pre:
                pre.left.next = pre.right
                if pre.next:
                    pre.right.next = pre.next.left
                pre = pre.next

            pre = pre_bakup.left

Idea

You traverse nodes in a zigzag-like path. For every node being visited, you set its left child’s next to right child. If the node itself has next node, then its right child should also point to the node’s next node’s left child.

Below is the traversal path of pre:

The idea uses O(1) space and O(N) time, where N is the number of nodes in the binary tree.

Reference: https://discuss.leetcode.com/topic/2202/a-simple-accepted-solution

Code (Using BFS, space complexity is O(N))

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

from collections import *

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None:
            return

        q = deque([(root, 0)])
        while q:
            if len(q) > 1:
                # if two nodes have the same level
                if q[0][1] == q[1][1]:
                    q[0][0].next = q[1][0]
            
            n, lvl = q.popleft()
            
            if n.left and n.right:
                q.append((n.left, lvl+1))
                q.append((n.right, lvl+1))            

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0        

        height_left, height_right = -1, -1
        
        node = root
        while node:
            height_left += 1 
            node = node.left
       
        node = root
        while node:
            height_right += 1
            node = node.right
       
        if height_left == height_right:
            return 2**(height_left+1) - 1
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Idea

height_left is the number of edges between root and its leftmost leaf. height_right is the number of edges between root and its rightmost leaf. If they are the same mean, that means the last level is full. Therefore we can return 2**(height_left+1)-1 by the property of binary tree. If height_left does not equal to height_right, then we have to recursively count the nodes in the left and right subtree.

The time complexity if O((logn)^2). This is because you need O(logn) to calculate height_left/height_right. After that, the worst case is that you need to recursively call self.countNodes(root.left) and self.countNodes(root.right). This happens no more than O(logn) times.

Reference:

https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.prev = None
        
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None: return
        self.flatten(root.right)
        self.flatten(root.left)
        # self.prev is root's left subtree's root
        root.right = self.prev
        root.left = None
        self.prev = root   

Idea

Create a variable self.prev, which records the current node (root)’s left subtree’s root. Overall it utilizes a post-order traversal. The algorithm first traverses right subtree then left subtree and finally adjusts the current root’s left and right subtree.

Reference: https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share/2

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        while root:
            ln = root.left
            if ln is not None:
                # find the right-most element of the left subtree 
                while ln.right:
                    ln = ln.right
                ln.right = root.right
                root.right = root.left
                root.left = None
            root = root.right

Idea

Iterative way. Time complexity is O(n) since every node can be set as root and ln no more than once.

Reference: https://discuss.leetcode.com/topic/3995/share-my-simple-non-recursive-solution-o-1-space-complexity

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

Code

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not str: 
            return True

        diff = 1
        for n in preorder.split(','):
            diff -= 1
            if diff < 0:
                return False
            if n != '#':
                diff += 2

        return diff == 0
     

Idea

Calculate the difference between in-degree and out-degree. See https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution 

Code

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        if not preorder: 
            return True
        
        stk = []
        nodes = preorder.split(',')
        for n in nodes:
            while stk and stk[-1] == '#' and n == '#':
                stk.pop()
                if not stk:
                    return False
                stk.pop()
            stk.append(n)
  
        return len(stk) == 1 and stk[0] == '#'

Idea

When you see two consecutive “#” characters (one on the top of stack and the other as the current node `n`), that means a subtree with two leaves has been scanned. Pop the subtree’s root as well as the ‘#’ on the stack and replace the topmost element on the stack with “#”.

See https://discuss.leetcode.com/topic/35977/simple-python-solution-using-stack-with-explanation and https://discuss.leetcode.com/topic/35973/java-intuitive-22ms-solution-with-stack

Code (BFS)

from collections import *
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0

        q = deque([(root, 1)])
        max_lvl = 1

        while q:
            node, lvl = q.popleft()
            max_lvl = max(max_lvl, lvl)
            if node.left is not None: 
                q.append((node.left, lvl+1))
            if node.right is not None:
                q.append((node.right, lvl+1))
            
        return max_lvl

Code (DFS)

from collections import *
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1 if root is not None else 0

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n².

Code

from heapq import *

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        # each element in the heap: (val, x coord, y coord)
        h = []

        for i in xrange(min(len(matrix[0]), k)):
            heappush(h, (matrix[0][i], 0, i))
        
        for i in xrange(k-1):
            val, x, y = heappop(h)
            if x < len(matrix)-1:
                heappush(h, (matrix[x+1][y], x+1, y)) 

        return h[0][0]

Idea

Maintain a min-heap with k element, initialized by the elements of the first row. Since it is a min-heap, and note the property that rows and columns are already sorted in ascending order, the heap root after popping k-1 times is the k-th smallest element of the whole matrix. When popping the heap, we also need to push necessary matrix elements into the heap.

You can imagine that when you traverse the matrix and maintain the heap, actually you are swiping through a sector area of the matrix, starting from the first row:

Space complexity is O(K) (heap size)

Time complexity is O(KlogK) (every heap operation takes O(logK))

Reference: https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code

Pythonically brute-force:

Code

from heaps import *
class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        return list(merge(*matrix))[k-1]

Note that each argument sent to heapq.merge should already be sorted from smallest to largest. (https://docs.python.org/2/library/heapq.html)

Binary Search

Code

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        left, right = matrix[0][0], matrix[n-1][n-1]
        while left < right:
            mid = left + (right - left)/2
            count = 0
            j = n-1
            for i in xrange(n):
                while j >=0 and matrix[i][j] > mid:
                    j -= 1
                count += j + 1
            if count >= k:
                right = mid
            else:
                left = mid + 1
        
        return left            
        

Idea:

We can eventually find the k-th smallest element by shrinking the search range in binary search. Binary search is feasible for this problem since left, right,and mid in binary search are integers and we know that matrix elements are integers. 

The algorithm takes O(nlogN) time (N is the range of matrix[0][0] ~ matrix[n-1][n-1]) and O(1) space.

Time complexity analysis: the outer loop (line 10-21) executes at most O(logN) times. The inner for loop (line 14-17) executes at most O(n) times.

Reference: https://discuss.leetcode.com/topic/52865/my-solution-using-binary-search-in-c/16

Also a much more complicated algorithm taking O(N) time: https://discuss.leetcode.com/topic/53126/o-n-from-paper-yes-o-rows

https://leetcode.com/problems/palindrome-number/

Code

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0 or (x > 0 and x % 10 == 0): 
            return False
        
        sum = 0
        while x > sum:
            sum = sum * 10 + x % 10
            x = x / 10
        
        return x == sum or x == (sum/10)

Idea

Create a variable, sum, that sums the digits reading from the right to left. Note that the while loop stops when x<=sum. Therefore, sum will never be larger than original x. This guarantees that `sum` will never cause overflow issue.  

The final return condition is x==sum or x==(sum/10). However, any number that is multiples of 10 also satisfies this condition. That is why we need to exclude multiples of 10 in line 7-8.

Reference:

https://discuss.leetcode.com/topic/8090/9-line-accepted-java-code-without-the-need-of-handling-overflow

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Code (recursion)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.recursion(root, 1, res)
        return res

    def recursion(self, node, level, res):
        if node is None:
            return res
        if len(res) < level:
            res.append(node.val)
        self.recursion(node.right, level+1, res)
        self.recursion(node.left, level+1, res)

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None: 
            return []
        
        res = []
        q = deque([(root, 0)])
        last_v = 0
        last_l = 0
        
        while q:
            n, l = q.popleft()
            if l > last_l:
                res.append(last_v)
            
            last_l = l
            last_v = n.val

            if n.left is not None:
                q.append((n.left, l+1))
            if n.right is not None:
                q.append((n.right, l+1))
        
        res.append(last_v)
        return res
        

Idea

Core idea is to have level recorded during traversal.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return (p is None and q is None) or (p is not None and q is not None and p. val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

Idea

Recursion is easy to implement for this problem.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        q1,q2 = deque([p]), deque([q])
        
        while stk1 and stk2:
            n1, n2 = q1.popleft(), q2.popleft()
            if (n1 is None and n2 is not None) or \
               (n1 is not None and n2 is None) or \
               (n1 and n2 and n1.val != n2.val):
                return False
                
            if n1 and n2:
                q1.append(n1.left)
                q2.append(n2.left)
                q1.append(n1.right)
                q2.append(n2.right)
            
        return True

Idea

Traverse two trees in same manner. Here I implement a bfs traverse.

Reference: https://discuss.leetcode.com/topic/7513/my-non-recursive-method (The author uses pre-order dfs)

        0
        |
        1
       / \
      2   3

     0  1  2
      \ | /
        3
        |
        4
        |
        5

Code

from collections import defaultdict

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 0: return []
        if n == 1: return [0]
        
        res = []
        adj = defaultdict(set)

        for e in edges:
           adj[e[0]].add(e[1])
           adj[e[1]].add(e[0])

        leaves = self.build_leaves_from_adj(adj)
        
        while n > 2:
            n = n - len(leaves)
            for l in leaves:
                adj[adj[l].pop()].remove(l)
                adj.pop(l)
            leaves = self.build_leaves_from_adj(adj)
        
        return leaves

    def build_leaves_from_adj(self, adj):
        return [k for k, v in adj.iteritems() if len(v) <= 1]
 

Idea

Imagine you are doing BFS from the current leaves. In every iteration, you remove all edges connected with leaves and leaf nodes themselves. Then, you re-identify new leaves. You repeatedly do this until at most two nodes left. The remaining nodes are the rooted nodes for MHT. 

Reference: 

https://discuss.leetcode.com/topic/30572/share-some-thoughts/2

Code

from collections import defaultdict

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 0: return []
        if n == 1: return [0]        

        res = []
        adj = defaultdict(set)

        for e in edges:
           adj[e[0]].add(e[1])
           adj[e[1]].add(e[0])

        max_path = self.maxpath(adj, edges[0][0], None)    
        max_path = self.maxpath(adj, max_path[-1], None)        
        l = len(max_path)

        if l % 2 == 0:
            return max_path[l/2-1:l/2+1]
        else:
            return max_path[l/2:l/2+1]        

    def maxpath(self, adj, cur_node, prev_node):
        max_path = [cur_node]
  
        for n in adj[cur_node]:
            # check whether the next visiting node is not visited before. 
            # use the property that tree has no cycle. just need to check with last visited node.
            if n != prev_node:
                new_max_path = [cur_node] + self.maxpath(adj, n, cur_node)    
                if len(max_path) < len(new_max_path):
                    max_path = new_max_path   
        return max_path
        

Idea (From https://discuss.leetcode.com/topic/30956/two-o-n-solutions)

Longest Path

It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree.
Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).

Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs).
The following is some thought of the latter.

Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.
Then y must be one of the endpoints on some longest path.
Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.

Now, the path from y to z is the longest one, and thus its middle point(s) is the answer.