Day 12 | 8/7

[tech-cow]

今日计划 | DFS Tree

搜集DFS资源，以及针对经典题开刷。

Leetcode

• 226. Invert Binary Tree
• 104. Maximum Depth of Binary Tree
• 559. Maximum Depth of N-ary Tree
• 110. Balanced Binary Tree
• 257. Binary Tree Paths
• 114. Flatten the Binary Tree to Linked List
• 270. Closest Binary Search Tree Value
• 235 Lowest Common Ancestor of a Binary Search Tree
• 236 Lowest Common Ancestor of a Binary Tree
• 230. Kth Smallest Element in a BST
• 98. Validate Binary Search Tree

[tech-cow]

Leetcode

226. Invert Binary Tree

类型：分制
Time Complexity O(n)
Space Complexity O(h)

这是一个post-order的处理，先找到左右的叶子节点，再返回之前，跟换左右node的位置。

DFS Recursive

class Solution(object):
    def invertTree(self, root):
        if not root: return
        root.left = self.invertTree(root.left)
        root.right = self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

BFS

class Solution(object):
    def invertTree(self, root):
        q = collections.deque([root])
        while q:
            node = q.popleft()
            if node:
                node.left, node.right = node.right, node.left
                q.append(node.left)
                q.append(node.right)
        return root

DFS Stack

class Solution(object):
    def invertTree(self, root):
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack.append(node.left)
                stack.append(node.right)
        return root

104. Maximum Depth of Binary Tree

类型：DFS遍历|分制
Time Complexity O(n)
Space Complexity O(h)

DFS遍历

储存全局变量，在每层DFS进行对全局变量的比对。

class Solution(object):
    def maxDepth(self, root):
        self.max_depth = 0
        self.dfs(root, 1)
        return self.max_depth
        
    def dfs(self, root, depth):
        if not root: return
        self.max_depth = max(depth, self.max_depth)
        self.dfs(root.left, depth + 1)
        self.dfs(root.right, depth + 1)

DFS分制

left和right用post-order的方法，先遍历到树的最底层(leaf)，然后从底层开始返回报告，最开始的第一层高度为
if not root: return 0，也就是0，然后没返回一层加一次。
之所以max(left, right) + 1 这里要加1，是因为我们第一层定义的高度为0，而不是1，少加了一层。

class Solution(object):
    def maxDepth(self, root):
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

559. Maximum Depth of N-ary Tree

类型：DFS遍历|分制
Time Complexity O(n)
Space Complexity O(h)

DFS遍历

104无脑变种

class Solution(object):
    def maxDepth(self, root):
        self.res = 0
        self.dfs(root, 1)
        return self.res
        
    def dfs(self, root, height):
        if not root: return
        self.res = max(self.res, height)
        for node in root.children:
            self.dfs(node, height + 1)

DFS分制

104 无脑变种

class Solution(object):
    def maxDepth(self, root):
        if not root: return 0
        if not root.children: return 1
        return max(self.maxDepth(node) for node in root.children) + 1

110. Balanced Binary Tree

类型：DFS分制
Time Complexity O(n)
Space Complexity O(h)

用了取巧的方法来表示是否高度大于1，这里只要高度大于1，就将每层的返回值设定为-1，如果最终返回到root的值没有-1，代表高度都小于1，但凡返回了-1，就证明这颗树在某一层出现unbalance的情况。

class Solution(object):
    def isBalanced(self, root):
        return self.dfs(root) != -1
    
    def dfs(self, root):
        if not root: return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        if abs(left - right) > 1 or left == -1 or right == -1:
            return -1
        return max(left, right) + 1

257. Binary Tree Paths

类型：DFS遍历 | 分制
Time Complexity O(n)
Space Complexity O(h)

DFS遍历

这里利用str是immutable的特性，不需要考虑每次backtrack时候对temp数组的更改。
递归思路三种：

1. 如果没有左右孩子：将temp存入返回数组res
   2/3: 如果有左或者右，递归并且更新temp

class Solution(object):
    def binaryTreePaths(self, root):
        if not root: return []
        res = []
        self.dfs(root, res, '')
        return res
    
    def dfs(self, root, res, temp):
        temp += str(root.val)
        if not root.left and not root.right:
            res.append(temp)
        if root.left:
            self.dfs(root.left, res, temp + '->')
        if root.right:
            self.dfs(root.right, res, temp + '->')

DFS分制

这里比较Tricky，先遍历到最下端，每次往上返回的是一个数组，数组里面包含了所有左边或者右边传上去的各种path，在上传到parent节点的时候，parent在所有的path里面迭代一次，反向加上当前root.val，然后继续晚上反。因为这里没有用全局的return value，每次在向上传递的时候，要重新再对return value进行append。

class Solution(object):
    def binaryTreePaths(self, root):
        if not root: return []
        res = []
        left_path = self.binaryTreePaths(root.left)
        right_path = self.binaryTreePaths(root.right)
        
        if not root.left and not root.right:
            res.append(str(root.val))
        
        if root.left:
            for path in left_path:
                path = str(root.val) + '->' + path 
                res.append(path)
        if root.right:
            for path in right_path:
                path = str(root.val) + '->' + path 
                res.append(path)
        return res

114. Flatten the Binary Tree to Linked List

类型：DFS遍历
Time Complexity O(n)
Space Complexity O(h)

通过储存一个全球变量，从最右边最下面的Node开始返回，每次返回的时候更新当前节点和全球变量的关系，具体可以看以下视频

公瑾讲解

class Solution(object):
    def __init__(self):
        self.prev = None
        
    def flatten(self, root):
        if not root: 
            return None
        
        self.flatten(root.right)
        self.flatten(root.left)
        
        root.right = self.prev
        root.left = None
        self.prev = root

270. Closest Binary Search Tree Value

类型：DFS遍历 | 分制
Time Complexity O(n)
Space Complexity O(h)

使用分治法:

1. target 比 root.val 小，往左子树找 abs(最大值-target) 并与 abs(root.val-target) 比大小；
2. target 比 root.val 大，往右子树找 abs(最小值-target) 并与 abs(root.val-target) 比大小；

返回条件：root节点会和左边和右边传上来最小的数比对。所以每次返回left最接近target的或者是right最接近target的数。

DFS分制

class Solution(object):
    def closestValue(self, root, target):
        if not root: return None
        if target < root.val:
            if root.left:
                left = self.closestValue(root.left, target)
                if abs(left - target) < abs(root.val - target):
                    return left
        if target > root.val:
            if root.right:
                right = self.closestValue(root.right, target)
                if abs(right - target) < abs(root.val - target):
                    return right
        return root.val

DFS遍历

Define一个方程内的全局变量，然后传入自方程去实现逻辑。
基本和上面思路一样，只是不需要返还值

class Solution(object):
    def closestValue(self, root, target):
        self.res = root.val
        self.dfs(root, target)
        return self.res
    
    
    def dfs(self, root, target):
        if not root: return None
        if abs(self.res - target) > abs(root.val - target):
            self.res = root.val
        if target < root.val:
            left = self.dfs(root.left, target)
        else:
            right = self.dfs(root.right, target)

235. Lowest Common Ancestor of a Binary Search Tree

类型：DFS分制
Time Complexity O(n)
Space Complexity O(h)

根据BST的特性，如果p和q里面最大的值都比root.val小的话，那证明p和q都在左边，所以往左边递归就行，右边递归道理相同。然后第三种case当root.val等于p和q之间一个的时候，直接返回root即可，因为找到了

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root: return None
        if max(p.val, q.val) < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if min(p.val, q.val) > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root   

236. Lowest Common Ancestor of a Binary Tree

类型：DFS分制
Time Complexity O(n)
Space Complexity O(h)

这道Follow Up没有BST的特性，所以要对几种case一个一个进行测试。
Condition为两种：如果没找到，返回None，找到则返回当前的root(因为找到一个root就不需要继续深入)
比对方式：

1. 如果parent的左右孩子都有返回，说明parent就是LCA
2. 如果左边没有返回：则右边返回的就是LCA
3. 如果右边没有返回：则左边返回的就是LCA

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if not root: return None
        if p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p , q)
        right = self.lowestCommonAncestor(root.right, p , q)
        
        if left and right:
            return root
        if not left:
            return right
        if not right:
            return left

230. Kth Smallest Element in a BST

类型：Inorder遍历
Time Complexity O(n)
Space Complexity O(h)

Inorder遍历

BST上升排序是根据Tree里面的Inorder，这里就按照Inorder走，然后当k==count的时候，返回当前root.val即可

class Solution(object):
    def kthSmallest(self, root, k):
        self.res = 0
        self.count = k
        self.inorder(root)
        return self.res
    
    def inorder(self, root):
        if not root: return
        self.inorder(root.left)
        self.count -= 1
        if self.count == 0:
            self.res = root.val
            return
        self.inorder(root.right)

98. Validate Binary Search Tree

类型：DFS遍历
Time Complexity O(n)
Space Complexity O(h)

O(N) Space解法：

利用数组储存inorder过的数，如果出现重复，或者数组不等于sorted(arr)，证明不是Valid Tree

class Solution(object):
    def isValidBST(self, root):
        self.arr = []
        self.inorder(root)
        return self.arr == sorted(self.arr) and len(self.arr) == len(set(self.arr))
    
    def inorder(self, root):
        if not root: return
        self.inorder(root.left)
        self.arr.append(root.val)
        self.inorder(root.right)

O(1) Space解法：

在上面的算法里进行了优化，每次只需要将当前root.val和上次储存的self.last比对即可知道是否满足条件。然后设立self.flag用于返回。

class Solution(object):
    def isValidBST(self, root):
        self.last = -float('inf')
        self.flag = True
        self.inorder(root)
        return self.flag
    
    def inorder(self, root):
        if not root: return
        self.inorder(root.left)
        if self.last >= root.val:
            self.flag = False
        self.last = root.val
        self.inorder(root.right)