Tree真题

[骨骼清奇]n-array tree, 给一个node 算出包括这个node在内的所有child的sum
[骨骼清奇]n-array tree，给一个node 打印出从这node出发的所有path. 问了时间复杂度和空间复杂度。
[骨骼清奇]第一轮问了两题，第一题是一个数组，在某个位置前元素单调递增，然后单调递减，就是那种元素大小像山一样形状的数组，然后求最大最小值，用binary search做，然后第二题是比较二叉树是否相同，问了一下时间复杂度。

[骨骼清奇]Write a function to detect if two trees are isomorphic.
给定两颗树，判断它们是否有相同的shape.
follow up：如果允许树的节点拥有任意数目的父节点，如何判断？
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
转移关系：1到n中选定某个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的根节点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的数值是0-N-1，构成一颗树，ans[i]表示从i出发到其他所有nodes的edges数之和。ans[0] = 1+1+2+2+2 = 8
重点是找到关系edge AB在最终答案里的关系：ans[B] = ans[A] + Nodes_A - Nodes_B。因为AB是直接相连的，那么从B出发，对于以B为根节点的nodes而言，ans[A]里面每一个都多加了1，那个1就是edgeAB，因此要减掉Nodes_B。同样的，ans[A]还需要加上Nodes_A, 因为从B出发需要经过BA，而从A出发不用。

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？其实是相对于root这个symmetric axis的位置，只要turn right就加一，turn left减一，再把这个表示相对位置的Index放入一个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出发，left child不停的入栈，直到遇到一个Node没有left child(可能是leaf也可能不是)，这就是我们in-order traversal的第一站，然后以它的left child作为root，重复刚刚那一套流程。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