树

1 二叉树的最近公共祖先（leetcode 236)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if (root is None) or (p is root) or (q is root):
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        if left and not right:
            return left
        else:
            return right

2 判断是否为平衡二叉树

class CheckBalance:
    def check(self, root):
        # write code here
        def depth(root):
            if root is None:
                return 0
            left = depth(root.left)
            right = depth(root.right)
            if abs(left - right) > 1:
                return -1
            return max(left+1, right+1)
        
        if depth(root) < 0:
            return False
        return True

3 判断二叉树是否为满二叉树

class CheckCompletion:
    def chk(self, root):
        # write code here
        if root is None:
            return True
        queue = []
        leafflag = 0
        queue.append(root)
        while len(queue):
            Node = queue.pop(0)
            if leafflag == 1:
                if Node.left or Node.right:
                    return False
                continue
            if Node.left:
                if Node.right:
                    queue.append(Node.left)
                    queue.append(Node.right)
                else:
                    leafflag = 1
            else:
                if Node.right:
                    return False
        return True

4 树节点间的最大距离

class LongestDistance:
    def findLongest(self, root):
        if root is None:
            return 0
        left = self.findLongest(root.left)
        right = self.findLongest(root.right)
        zhong = self.depth(root.left) + self.depth(root.right) + 1
        return max(left, right, zhong)
    def depth(self, root):
        if root is None:
            return 0
        left = self.depth(root.left)
        right = self.depth(root.right)
        return max(left,right) + 1

5 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置

class FindErrorNode:
    def findError(self, root):
        # write code here
        middle_order = self.Middle(root)
        decrease_count = 0
        return_list = []
        for i in range(1,len(middle_order)):
            if middle_order[i]<middle_order[i-1]:
                decrease_count+=1
                return_list.append([middle_order[i-1],middle_order[i]])
        if decrease_count == 2:
            result = [max(return_list[0]),min(return_list[1])]
        if decrease_count == 1:
            result = [max(return_list[0]),min(return_list[0])]
        return [min(result),max(result)]
             
    def Middle(self,root):
        stack = []
        return_list = []
        x = root
        while (len(stack) or x):
            if x != None:
                stack.append(x)
                x = x.left
            else:
                temp = stack.pop()
                return_list.append(temp.val)
                x = temp.right
        return return_list

6 validate binary search tree

#method1 中序遍历
def isValidBST(self, root):
    inorder = self.inorder(root)
    return inorder == list(sorted(set(inorder)))
def inorder(self, root):
    if root is None:
        return []
    return self.inorder(root.left)+[root.val]+self.inorder(root.right)

#method2 
def isValidBST(self, root):
    self.prev = None
    return self.helper(root)

def helper(self, root):
    if root is None:
        return True
    if not self.helper(root.left):
        return False
    if self.prev and self.prev.val >= root.val:
        return False
    self.prev = root
    return self.helper(root.right)