算法-数据结构-树

算法

1. 判断是否二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None


class Solution:
    node_list=[]
    return_flag=True
    def isValidBST(self, root: TreeNode) -> bool:
        self.in_order(root)
        return self.return_flag

    def in_order(self,root):
        if root is None: return
        self.isValidBST(root.left)
        if not self.node_list or self.node_list[-1]<root.val:
            self.node_list.append(root.val)
        else:
            self.node_list.append(root.val)
            self.return_flag= False
            return
        self.isValidBST(root.right)

2. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None or root.val ==q or root.val==p : return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right= self.lowestCommonAncestor(root.right,p,q)
        if left is None:
            return right
        elif right is None:
            return left
        else:
            return root.val

3. 二叉树广度优先遍历 BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def BFS(root):

    q=[]
    q.append(root)
    num=[]

    while q:
        size=len(q)

        current_num=[]
        for i in range(size):
            root=q.pop(0)
            current_num.append(root.data)
            if root.left_child is not None: q.append(root.left_child)
            if root.right_child is not None: q.append(root.right_child)
        num.append(current_num)

    return num

4. 二叉树深度优先遍历 DFS

1
2
3
4
5
6
def DFS(root):
    if root is None:
        return
    print(root.data)
    if root.left_child is not None: DFS(root.left_child)
    if root.right_child is not None: DFS(root.right_child)

1.二叉树

  1. 构建二叉查找树
  2. 先序遍历
  3. 中序遍历
  4. 后序遍历
  5. 构建平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class TreeNode():
    
    def __init__(self,x):
        self.left_child=None
        self.right_child=None
        self.data=x

class Tree():

    def __init__(self,x):
        self.tree_data=[]
        self.root=None

    def insert(self,root,x):
        """ 构造二叉查找树 """
        if root is None:
            return TreeNode(x)
        if root.data > x:
            root.left_child=self.insert(root.left_child,x)
        else:
            root.right_child=self.insert(root.right_child,x)
        return root

    def preorder(slef,root):
        “”“ 先序遍历 ”“”
        if not root : return
        self.tree_data.append(root.data)
        self.preorder(root.left_child)
        self.preorder(root.right_child)

    def inorder(slef,root):
        “”“ 中序遍历 ”“”
        if not root : return
        self.inorder(root.left_child)
        self.tree_data.append(root.data)
        self.inorder(root.right_child)

    def postorder(slef,root):
        “”“ 后序遍历 ”“”
        if not root : return
        self.postorder(root.left_child)
        self.postorder(root.right_child)
        self.tree_data.append(root.data)

    def insert2(self,root,x):
        """ 构建平衡二叉树 """
        if root is None:
            return TreeNode(x)

        tree_node=[root]
        wile True:
            node=tree_node.pop(0)
            if node.left_child is None:
                node.left_child=TreeNode(x)
                return root
            elif node.right_child is None:
                node.right_child=TreeNode(x)
                return root
            else:
                tree_node.append(node.left_child)
                tree_node.append(node.right_child)


2.树的子节点(判断是不是一颗树的子树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subTree(root,sub_root):
    if root is None or sub_root is None:
        return false

    return isSubTree(root,sub_root) || subTree(root.left,sub_root) || subTree(root.right,sub_root)

def isSubTree(root,sub_root):
    if sub_root is None:
        return True
    if root is None:
        return False
    if root.data!= sub_root.data:
        return False
    return isSubTree(root.left,sub_root.left) and isSubTree(root.right,sub_root.right)

3.二叉树的镜像

1
2
3
4
5
6
7
8
9
def mirror(root)
    if root is None:
        return
    swap(root)
    mirror(root.left)
    mirror(root.right)

def swap(root)
    root.left,root.right=root.right,root.left

4.判处是否是对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
def subTree(root):
    if root is None:
        return false
    return isSubTree(root.eft,root.right)

def isSubTree(root,sub_root):
    if sub_root is None:
        return True
    if root is None:
        return False
    if root.data!= sub_root.data:
        return False
    return isSubTree(root.left,sub_root.left) and isSubTree(root.right,sub_root.right)