二叉树

发表于

二叉树的定义：

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

二叉树的特点：

  • 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质：

  • 在二叉树的第i层上最多有2i-1个节点 。（i>=1）
  • 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
  • n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
  • 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。

遍历二叉树:

前序遍历：根 -> 左 -> 右（前中后是指的是根的位置）

中序遍历：左 -> 根 -> 右

后序遍历：左 -> 右 -> 根

层次遍历：自上而下遍历

栈的相关问题：

重建二叉树：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：前序的第一个结点为根结点，可以将中序遍历分为左子树和右子树。递归调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if len(pre) ==0:
            return None
        root = TreeNode(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
        root.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
        return root

二叉树的下一个结点：

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：

1.如果结点有右子树，那么这个结点的下一个结点的右子树的最左结点

2.如果结点没有有右子树，就要向上找第一个左链接指向的树包含该结点的祖先结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        while pNode.next :
            #这是判断这个结点是不是左孩子的意思
            if pNode.next.left == pNode:
                return pNode.next
            pNode = pNode.next
        return None

对称的二叉树：

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：前序遍历是：根左右；前序遍历的对称是：根右左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        return self.Symmetrical(pRoot,pRoot)
    def Symmetrical(self,root1,root2):
        if root1 == root2 and root2 == None:
            return True
        if root1 == None or root2 == None:
            return False
        if root1.val != root2.val:
            return False
        return self.Symmetrical(root1.left,root2.right)and self.Symmetrical(root1.right,root2.left)

按之字形顺序打印二叉树：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：

奇数层：从左到右

偶数层：从右到左

所以我们使用两个栈，在打印某一行的结点的时候，把下一层的子结点保存在相对应的栈中。如果现在打印的是奇数层，说明下一层偶数层（从右到左），要先把左子树结点压入再把右子树结点压入第一个栈里面；反之偶数层，先保存右子树再保存左子树。

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        result,nodes = [],[pRoot]
        right = True
        while nodes:
            curStack,nextStack = [],[]
            if right:
                for node in nodes:
                    curStack.append(node.val)
                    if node.left:
                        nextStack.append(node.left)
                    if node.right:
                        nextStack.append(node.right)
            else:
                for node in nodes:
                    curStack.append(node.val)
                    if node.right:
                        nextStack.append(node.right)
                    if node.left:
                        nextStack.append(node.left)
            nextStack.reverse()
            right = not right
            result.append(curStack)
            nodes = nextStack 
        return result

把二叉树打印成多行：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：使用队列进行层次遍历。一个队列就足够了，当前队列中的结点数就是当前层的结点数，控制只遍历这么多结点数，然后他们的子结点插入到队列。

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        queue = [pRoot]
        result = []
        while queue:
            row=[]
            for i in queue:
                row.append(i.val)
            result.append(row)
            
            for i in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

序列化二叉树：

请实现两个函数，分别用来序列化和反序列化二叉树

思路：前序遍历序列化二叉树，结点间添加“，”隔开。

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#,'
        return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        self.flag += 1
        l = s.split(',')
        
        if self.flag >=len(s):
            return None
        root = None
        
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

二叉搜索树的第k个结点：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路：二叉搜索树的中序遍历有序

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
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        #中序遍历
        if not pRoot:
            return None
        results = self.midsearch(pRoot)
        if k<=0 or k>len(results):
            return None
        else:
            return results[k-1]
        
        
        
    def midsearch(self,pRoot):
        result = []
        if not pRoot:
            return None
        if pRoot.left:
            result.extend(self.midsearch(pRoot.left))
        result.append(pRoot)
        if pRoot.right:
            result.extend(self.midsearch(pRoot.right))
        return result

树的子结构：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：B是A的根结点，左子树，右子树其中一个就行

A要满足根结点，左孩子右孩子都一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        return self.isSubtree(pRoot1,pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)
    
    def isSubtree(self,a,b):
        if not b :
            return True
        if not a or a.val != b.val:
            return False
        return self.isSubtree(a.left,b.left) and self.isSubtree(a.right,b.right)

二叉搜索树的后序遍历序列:

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：递归判断左右子树是不是二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        if len(sequence)==1 or len(sequence)==2:
            return True
        root = sequence.pop(-1)
        sign = 0
        for i in range(len(sequence)):
            if sequence[i] > root:
                sign = 1
            if (sign ==1) and (sequence[i] < root):
jiedid                return False //遇见了比root大的说明一定是右孩子，如果是二叉树的后序遍历右孩子的后面结点一定比根大
        return self.VerifySquenceOfBST(sequence[i:]) and self.VerifySquenceOfBST(sequence[:i])

二叉树中和为某一值的路径：

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：DFS深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        if root and not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        res = []
        left = self.FindPath(root.left,expectNumber-root.val)
        right= self.FindPath(root.right,expectNumber-root.val)
        for i in left+right:
             res.append([root.val]+i)
        return res

二叉树的深度：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        return 1+max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))

平衡二叉树：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：平衡二叉树的左右子树高度相差不超过1.使用递归左右子树也需要是平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here、
        if not pRoot:
            return True
        if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left)and self.IsBalanced_Solution(pRoot.right)
     
    def TreeDepth(self,pRoot):
        if not pRoot:
            return 0
        return max(1+self.TreeDepth(pRoot.right),1+self.TreeDepth(pRoot.left))