05Tree树

由节点(node)组成，每个节点有零个或多个子节点(child node)，没有父节点的是根节点(root node)，每个非根节点只有一个父节点(parent root)，没有任何子节点的节点叫叶子节点(leaf node)，一棵树中，只有一个root node

二叉树(binary tree)
每个节点最多有两个子节点，两个子节点分别被称为左孩子(left child)和右孩子(right child)，叶子节点：没有孩子节点的节点

子树(sub-tree)
树中的每个节点代表以它为根的一颗树，左孩子所代表的树称为左子树(left sub-tree)，右孩子所代表的树称为右孩子树(right sub-tree)

文件系统：B+树
字典树，平衡树

二叉树的遍历
先序遍历 根左右
中序遍历 左根右
后序遍历 左右根

递归
数据结构的递归 树就是一种递归的数据结构
算法(程序)的递归 函数自己调用自己

递归的三要素
递归的定义 首先这个问题或者数据结构得是递归定义的
递归的出口 什么时候递归终止
递归的拆解 递归不中值的时候，如何分解问题

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)

node1.left = node2
node1.right = node3

print(node1)
print(node2)
print(node3)

# 斐波那契数列
class Solution:
    def fibonacci(self, n):
        if n == 1:
            return 0
        if n == 2:
            return 1
        return self.fibonacci(n - 1) + self.fibonacci(n - 2)


s = Solution()
print(s.fibonacci(10))

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


def myPrint(node):
    '''先序遍历'''
    if node is None:
        return
    print(node.val)
    myPrint(node.left)
    myPrint(node.right)


node1 = TreeNode(3)
node2 = TreeNode(1)
node3 = TreeNode(4)
node4 = TreeNode(6)
node5 = TreeNode(7)

node1.left = node2
node1.right = node4
node4.left = node3
node4.right = node5
myPrint(node1)

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


def myPrint(node):
    '''中序遍历'''
    if node is None:
        return
    myPrint(node.left)
    print(node.val)
    myPrint(node.right)


node1 = TreeNode(3)
node2 = TreeNode(1)
node3 = TreeNode(4)
node4 = TreeNode(6)
node5 = TreeNode(7)

node1.left = node2
node1.right = node4
node4.left = node3
node4.right = node5
myPrint(node1)

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


def myPrint(node):
    '''后序遍历'''
    if node is None:
        return
    myPrint(node.left)
    myPrint(node.right)
    print(node.val)


node1 = TreeNode(3)
node2 = TreeNode(1)
node3 = TreeNode(4)
node4 = TreeNode(6)
node5 = TreeNode(7)

node1.left = node2
node1.right = node4
node4.left = node3
node4.right = node5
myPrint(node1)

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


class Solution:
    '''求所有叶子节点的和'''
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

    def leafSum(self, root):
        '''时间复杂度为O(n)'''
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return root.val
        return self.leafSum(root.left) + self.leafSum(root.right)


s1 = Solution(1)
s2 = Solution(2)
s3 = Solution(3)
s4 = Solution(4)

s1.left = s2
s1.right = s3
s2.left = s4
print(s1.leafSum(s1))

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


class Solution:
    '''树的最大深度'''
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

    def maxDepth(self, root):
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 1
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1


s1 = Solution(1)
s2 = Solution(2)
s3 = Solution(3)
s4 = Solution(4)
s5 = Solution(5)
s1.left = s2
s1.right = s3
s3.left = s4
s3.right = s5
print(s1.maxDepth(s1))

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

    def __str__(self):
        return "{val:%s, left:%s, right:%s}" % (self.val, self.left, self.right)


# 判断两棵树是否同构，同构的定义是判断两棵树是否完全相同
class Solution:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

    def isIdentical(self, a, b):
        if a is None and b is None:
            return True
        if a is not None and b is None:
            return False
        if a is None and b is not None:
            return False
        return a.val == b.val and self.isIdentical(a.left, b.left) and self.isIdentical(a.right, b.right)


a1 = Solution(1)
a2 = Solution(2)
a3 = Solution(2)
a4 = Solution(4)
a1.left = a2
a1.right = a3
a2.left = a4

b1 = Solution(1)
b2 = Solution(2)
b3 = Solution(2)
b4 = Solution(4)
b1.left = b2
b1.right = b3
b2.left = b4

print(a1.isIdentical(a1, b1))