由节点(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))
网友评论