[数据结构与算法]牛客网视频总结5(二叉树)

牛客网视频总结5

二叉树先序、中序、后序遍历

先序遍历：先打印当前节点，然后打印整棵左子树，然后打印右子树
中序遍历：先打印左节点，然后打印当前节点，然后右节点
后序遍历：先打印左节点，然后打印右节点，最后打印当前节点

递归方法

中序遍历为例，先序遍历就把append放前面，后续遍历就放后面

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        def find(root):
            if root == None:
                return;
            else:
                find(root.left)
                result.append(root.val)
                find(root.right)
        find(root)
        return result

非递归方法

中序遍历：建立一个栈结构
如果当前节点不为空，则压一个进栈，当前节点向左走
如果当前节点为空，从栈里拿一个出来，当前节点向右走

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Stack(object):
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
    def pop(self):
        tem = self.stack[-1]
        self.stack = self.stack[0:-1]
        return tem
    def isEmpty(self):
        return len(self.stack)==0

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = Stack()
        result = []
        while (root!=None) or (not stack.isEmpty()):
            if root != None:
                stack.push(root)
                root = root.left
            else:
                root = stack.pop()
                result.append(root.val)
                root = root.right
        return result

先序遍历(中左右)：

• head出栈
• 右子树不空，压
• 左子树不空，压

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Stack(object):
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
    def pop(self):
        tmp = self.stack[-1]
        self.stack = self.stack[0:-1]
        return tmp
    def isEmpty(self):
        return len(self.stack)==0

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = Stack()
        result = []
        while root!=None or not stack.isEmpty():
            if root != None:
                result.append(root.val)
                stack.push(root.right)
                stack.push(root.left)
            root = stack.pop()
        return result

后序遍历(左右中)：

• head出栈
• 左子树不空，压
• 右子树不空，压
• 先变成中右左的格式，然后再放到另外一个栈里输出左右中

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Stack(object):
    def __init__(self):
        self.stack = []
    def push(self, x):
        self.stack.append(x)
    def pop(self):
        tmp = self.stack[-1]
        self.stack = self.stack[0:-1]
        return tmp
    def isEmpty(self):
        return len(self.stack)==0

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = Stack()
        result = []
        stack_help = Stack()
        
        while root!=None or not stack.isEmpty():
            if root != None:
                stack_help.push(root)
                stack.push(root.left)
                stack.push(root.right)
            root = stack.pop()
        
        while not stack_help.isEmpty():
            result.append(stack_help.pop().val)

        return result

二叉树的后继节点/先驱节点

后继节点

中序遍历时，node的下一个节点叫后继节点，前一个节点叫先驱节点，比普通二叉树多了一个parent指针。

• 如果一个节点X有右子树，那么后继结点就是右子树的最左节点
• 如果X没有右子树，判断X为哪颗树左子树的最后一个节点：X为父节点的右孩子，再往上找，直到找到某个节点为父节点的左孩子；X为父节点的左孩子，父节点就是后继节点

前驱节点

• 如果一个节点X有左子树，那么前驱节点就是左子树的最右节点
• 如果X没有左子树，判断X为哪个树的右孩子：X为父节点的左孩子，再往上找，直到找到某个节点为父节点的右孩子；X为父节点的右孩子，父节点就是前驱节点

二叉树的序列化和反序列化

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Queue(object):
    def __init__(self):
        self.queue = []
    def push(self,x):
        self.queue.append(x)
    def pop(self):
        tmp = self.queue[0]
        self.queue = self.queue[1:]
        return tmp
    def isEmpty(self):
        return len(self.queue)==0

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        result = ''
        queue = Queue()
        while root!=None or not queue.isEmpty():
            if root!=None:
                queue.push(root.left)
                queue.push(root.right)
                result += (str(root.val) + ',')
            else:
                result += 'null,'
            root = queue.pop()
        result += 'null'
        return result
        
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        result = data.split(',')
        if result[0] == 'null':
            return []

        for i in range(len(result)):
            if result[i] != 'null':
                result[i] = TreeNode(val=result[i])

        nums_null = 0
        node = result[0]
        cur_node = node

        for i in range(len(result)):
            cur_node = result[i]
            if cur_node!= 'null':
                if result[2*i+1-2*nums_null] != 'null':
                    cur_node.left = result[2*i+1-2*nums_null]
                if result[2*i+2-2*nums_null] != 'null':
                    cur_node.right = result[2*i+2-2*nums_null]
            else:
                nums_null += 1
        return node
        

        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

判断二叉树是否为平衡二叉树（树型DP）

小套路（高度）：用递归函数，会回到某个节点3次
本题：判断以每个节点为头部的整棵树是否平衡

• 左树是否平衡
• 右树是否平衡
• 左树的高度
• 右树的高度

判断二叉树是否为搜索二叉树

搜索二叉树：每个节点的左节点比当前值小，右节点比当前值大
答：中序遍历的结果是依次升序的，则为搜索二叉树

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        result = []
        def findInOrder(root):
            if root == None:
                return;
            findInOrder(root.left)
            result.append(root.val)
            findInOrder(root.right)

        findInOrder(root)
        for i in range(len(result)-1):
            if result[i]>=result[i+1]:
                return False
        return True

判断二叉树是否为完全二叉树

• 如果一个节点有右孩子没有左孩子，直接返回false
• 如果一个节点左右孩子不双全(左有右没有/左右都没有)，后面遇到的节点都是叶节点

完全二叉树，求节点个数

满二叉树(L层)，节点个数$2^L?1$

• 先遍历左边界，记录深度h
• 再遍历右子树的左边界：如果深度为h，则证明左子树是满的，那么递归这个右子树就行了；如果深度为h-1，则证明右子树是满的(深度h-1)，那么递归左子树就行