[骨骼清奇]n-array tree, 給一個(gè)node 算出包括這個(gè)node在內(nèi)的所有child的sum
[骨骼清奇]n-array tree统扳，給一個(gè)node 打印出從這node出發(fā)的所有path. 問了時(shí)間復(fù)雜度和空間復(fù)雜度菩收。
[骨骼清奇]第一輪問了兩題填硕，第一題是一個(gè)數(shù)組盅粪，在某個(gè)位置前元素單調(diào)遞增堪夭，然后單調(diào)遞減咏删，就是那種元素大小像山一樣形狀的數(shù)組惹想，然后求最大最小值，用binary search做督函，然后第二題是比較二叉樹是否相同嘀粱，問了一下時(shí)間復(fù)雜度。

[骨骼清奇]Write a function to detect if two trees are isomorphic.
給定兩顆樹辰狡，判斷它們是否有相同的shape.
follow up：如果允許樹的節(jié)點(diǎn)擁有任意數(shù)目的父節(jié)點(diǎn)锋叨，如何判斷？
Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

def isIsomorphic(n1, n2): 
    if n1 is None and n2 is None: 
        return True
  
    if n1 is None or n2 is None: 
        return False
  
    if n1.data != n2.data : 
        return False

    # Case 1: subtrees NOT  "Flipped". 
    # Case 2: subtrees "Flipped" 
    return ((isIsomorphic(n1.left, n2.left)and 
            isIsomorphic(n1.right, n2.right)) or
            (isIsomorphic(n1.left, n2.right) and 
            isIsomorphic(n1.right, n2.left)) 
            ) 

Time Complexity: The above solution does a traversal of both trees. So time complexity is O(m + n) where m and n are number of nodes in given trees.

Follow up: general tree?
If swap with either two siblings, then we can compare level by level using permutation of node values.

LC 226 Invert Binary Tree 二叉樹的鏡像（Symmetric Tree）
Recursion:

class Solution:
    def Mirror(self, root):
        if root == None:
            return 
        self.Mirror(root.left)
        self.Mirror(root.right)
        root.left,root.right = root.right,root.left

Iterative way:
The idea is that we need to swap the left and right child of all nodes in the tree. So we create a queue to store nodes whose left and right child have not been swapped yet. Initially, only the root is in the queue. As long as the queue is not empty, remove the next node from the queue, swap its children, and add the children to the queue. Null nodes are not added to the queue. Eventually, the queue will be empty and all the children swapped, and we return the original root.

class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        level=[root]
        while level:
            for node in level:
                node.left,node.right = node.right,node.left
            level = [kid for node in level for kid in (node.left,node.right) if kid]
        return root

LC 102Binary Tree Level Order Traversal

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        ans,level = [],[root]
        while level:
            ans.append([node.val for node in level])
            level = [ kid for n in level for kid in (n.left,n.right) if kid]
        return ans

LC 105. Construct Binary Tree from Preorder and Inorder Traversal

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            root_ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[root_ind])
            root.left = self.buildTree(preorder, inorder[0:root_ind])
            #preorder now only contains nodes in right sub-tree of root
            root.right = self.buildTree(preorder, inorder[root_ind+1:])
            return root

LC 106. Construct Binary Tree from Inorder and Postorder Traversal

class Solution:
    def buildTree(self, inorder, postorder):
        if inorder:
            root_ind = inorder.index(postorder.pop())
            root = TreeNode(inorder[root_ind])
            root.right = self.buildTree(inorder[root_ind+1:],postorder)
            root.left = self.buildTree(inorder[:root_ind],postorder)
            return root

[骨骼清奇] LC 96 Unique Binary Search Trees
轉(zhuǎn)移關(guān)系：1到n中選定某個(gè)i作為root宛篇！

class Solution: #beat 100%
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<1: return 0
        F = [0]*(n+1)
        F[0] = F[1] = 1
        for i in range(2,n+1):
            for j in range(i):
                F[i] += F[j]*F[i-j-1]
        return F[n]

LC95 unique binary search tree II
需要返回所有不同BST的根節(jié)點(diǎn)list. 用Recursion做娃磺。

class Solution:
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        def generate_trees(start, end):
            if start > end:
                return [None,]
            
            all_trees = []
            for i in range(start, end + 1):  # pick up a root
                # all possible left subtrees if i is choosen to be a root
                left_trees = generate_trees(start, i - 1)
                
                # all possible right subtrees if i is choosen to be a root
                right_trees = generate_trees(i + 1, end)
                
                # connect left and right subtrees to the root i
                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)
            
            return all_trees
        
        return generate_trees(1, n) if n else []

[骨骼清奇] LC 834 Sum of Distances in Tree
Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Nodes的數(shù)值是0-N-1，構(gòu)成一顆樹叫倍，ans[i]表示從i出發(fā)到其他所有nodes的edges數(shù)之和偷卧。ans[0] = 1+1+2+2+2 = 8
重點(diǎn)是找到關(guān)系edge AB在最終答案里的關(guān)系：ans[B] = ans[A] + Nodes_A - Nodes_B。因?yàn)锳B是直接相連的吆倦，那么從B出發(fā)听诸，對于以B為根節(jié)點(diǎn)的nodes而言，ans[A]里面每一個(gè)都多加了1蚕泽，那個(gè)1就是edgeAB晌梨，因此要減掉Nodes_B。同樣的须妻，ans[A]還需要加上Nodes_A, 因?yàn)閺腂出發(fā)需要經(jīng)過BA仔蝌，而從A出發(fā)不用。

class Solution:
    def sumOfDistancesInTree(self, N, edges):
        """
        :type N: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        graph = self.buildGraph(N,edges)
        seen = set()
        cnts = [1]*N
        dist = [0]*N
        self.dfs(graph,0,dist,cnts,seen)
        #dist[0] is the chosen root and it is answered now!
        seen = set() 
        self.dfs2(graph,0,dist,cnts,seen,N)
        return dist

    def buildGraph(self,N,edges):
        from collections import defaultdict
        graph = defaultdict(list)
        for i,j in edges:
            graph[i].append(j)
            graph[j].append(i)
        return graph


    def dfs(self,graph,i,dist,cnts,seen):
        seen.add(i)
        for j in graph[i]:
            if j in seen:continue
            self.dfs(graph,j,dist,cnts,seen)
            cnts[i] += cnts[j]
            dist[i] += dist[j] + cnts[j]
            #cnts[j] means node i is one edge further
 
    def dfs2(self,graph,i,dist,cnts,seen,n):
        seen.add(i)
        for j in graph[i]:
            if j in seen:continue
            dist[j] = dist[i] - cnts[j] + (n - cnts[j])
            self.dfs2(graph,j,dist,cnts,seen,n)

https://blog.csdn.net/tinkle181129/article/details/79326023

[Uber] LC 314 Binary Tree Vertical Order Traversal
分析：如何判斷nodes屬于同一層vertical Order荒吏？其實(shí)是相對于root這個(gè)symmetric axis的位置敛惊，只要turn right就加一，turn left減一司倚，再把這個(gè)表示相對位置的Index放入一個(gè)hash table豆混，然后按照index從小打到輸出即可篓像！

from collections import deque, defaultdict

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        table = defaultdict(list)
        queue = deque()

        # put node and the level that it belongs to
        queue.append((root, 0))
        Gmin = Gmax = 0
        while queue:
            node, index = queue.popleft()
            if index<Gmin:Gmin = index
            if index>Gmax:Gmax = index
            table[index].append(node.val)

            if node.left:
                queue.append((node.left, index-1))

            if node.right:
                queue.append((node.right, index+1))

        # The keys of the table are the indices, sort it min to max
        # return [table[index] for index in sorted(table)]

        return [table[index] for index in range(Gmin,Gmax+1)]

LC 101 Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
General Tree:
left = arr[:len(arr)//2]
right = arr[:len(left):-1]

[骨骼清奇]考察二叉樹，自己定義tree node皿伺，然后自己把二叉樹各種遍歷方法寫一下员辩，遞歸的和非遞歸的。

LC 94 Binary Tree Inorder Traversal
Recursion:

def inorderTraversal1(self, root):
    res = []
    self.helper(root, res)
    return res
    
def helper(self, root, res):
    if root:
        self.helper(root.left, res)
        res.append(root.val)
        self.helper(root.right, res)

Iterative (stack)：從root出發(fā)鸵鸥，left child不停的入棧奠滑，直到遇到一個(gè)Node沒有l(wèi)eft child(可能是leaf也可能不是)，這就是我們in-order traversal的第一站妒穴，然后以它的left child作為root宋税，重復(fù)剛剛那一套流程。For each leaf, its left null child will help print the value of itself, and its null right child will help print the correspondent successor (could be an ancestor far above).

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stk = []
        ans = []
        node = root    
        while (node is not None) or stk:  # empty lists are falsy
            if node is not None:
                stk.append(node)
                node = node.left
            else:
                node = stk.pop()
                ans.append(node.val)
                node = node.right
        return ans

LC 230 Kth Smallest Element in a BST

class Solution:

    def kthSmallest(self, root, k):
        self.k = k
        self.in_order(root)
        return self.result

    def in_order(self, node):
        if not node:
            return None
        self.in_order(node.left)
        self.k -= 1
        if self.k == 0:
            self.result=node.val
            return
        self.in_order(node.right)

Iterative:

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        cnt,stack = 0,[]
        node = root
        while node is not None or stack:
            if node is not None:
                stack.append(node)
                node=node.left
            else:
                node=stack.pop()
                cnt += 1
                if cnt==k: return node.val
                node=node.right

LC 144 Binary Tree Preorder Traversal
Beat 100%

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans,stack = [],[]
        node = root
        while node is not None or stack:
            if node is not None:
                ans.append(node.val)
                #get value before going to children
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                node=node.right
        return ans

LC 145 Binary Tree Postorder Traversal

class Solution:
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        ans,stack = [],[]
        node = root
        while node is not None or stack:
            if node is not None:
                #ans.insert(0,node.val) #reverse preorder
                ans.append(node.val)
                stack.append(node)
                node = node.right #reverse preorder
            else:
                node = stack.pop()
                node = node.left #reverse preorder
        return ans[::-1]

[Uber]LC 450 Delete Node in a BST

1.When found the node, put right child of the node to the right of [the right most leaf node of left child][max value of left sub-tree but still smaller then any value in right sub tree]. That way the values are still in order.
2.Return the left child of the node(skip root, a.k.a delete it). If the node doesn't have left child, return right child.
3.Otherwise do binary search. If key < root.val, change left child to the returned new root. Do right child if key > root.val.

This solution always runs in O(log(n)) time since when it finds the node to delete, it goes to the right most leaf of the left sub-tree to put right sub-tree of the node there.

Modify and not return any node in recursion, beat 100%!

class Solution:
    def deleteNode(self, root, key):
        dummy = TreeNode(float('INF'))
        dummy.left = root
        self.replace(dummy,root,key)
        return dummy.left

    def replace(self,prev,cur,key):
        if not cur: return
        if cur.val<key:
            self.replace(cur,cur.right,key)
        elif cur.val>key:
            self.replace(cur,cur.left,key)
        else:#FOUND
            if cur.left:
                left_right_most = cur.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                left_right_most.right=cur.right
            
            if prev.val<key:
                prev.right = cur.left or cur.right
            else:
                prev.left = cur.left or cur.right

Slower Version without prev

class Solution(object):
    def deleteNode(self, root, key):
        if not root: return None
        
        if root.val == key:
            if root.left:
                # Find the right most leaf of the left sub-tree
                left_right_most = root.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                # Attach right child to the right of that leaf
                left_right_most.right = root.right
                # Return left child instead of root, a.k.a delete root
                return root.left
            else:
                return root.right
        # If left or right child got deleted, the returned root is the child of the deleted node.
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
            
        return root

[GoogleCall]Delete Treenode, all are put in an array. parent 0 has children 1 and 2.

LC 428 N-ary tree