二叉树

发表于 | 分类于 ， | 评论数：

重建二叉树

题目

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

思路

通常树有如下几种遍历方式：

  • 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
  • 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
  • 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。

本题为前序遍历和中序遍历，最少需要两种遍历方式，才能重建二叉树。

前序遍历序列中，第一个数字总是树的根结点的值。在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。剩下的我们可以递归来实现

1589703994496

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        # 判断树的长度
        if len(pre) == 0:
            return None
        elif len(pre) == 1:
            return TreeNode(pre[0])
        else:
            # 先根据先序遍历的结果，直接拿到根元素的内容
            root = TreeNode(pre[0])
            # 通过中序遍历知道左树和右树的分界线
            pos = tin.index(pre[0])
            # 通过递归的方法获取左子树和右子树
            root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
            root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])
        return root

树的子结构

题目

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

思路

要查找树A中是否存在和树B结构一样的子树，我们可以分为两步：
第一步在树A中找到和B的根结点的值一样的结点R，
第二步再判断树A中以R为根节点的子树是不是包含和树B一样的结构。

这里使用递归的方法即可。

代码

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.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2) or self.is_subtree(pRoot1, pRoot2)
    def is_subtree(self, A, B):
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.is_subtree(A.left, B.left) and self.is_subtree(A.right, B.right)

二叉树镜像

题目

操作给定的二叉树，将其变换为源二叉树的镜像。

思路

先交换根节点的两个子结点之后，我们注意到值为10、6的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后，我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示：

1589704091272

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root:
            return root
        left = root.left
        right = root.right
        tmp = left
        root.left = root.right
        root.right = tmp
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

从上往下打印二叉树

题目

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路

用一个数组来缓存每一层的节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        if not root:
            return []
        result = []
        tmp = [root]
        while tmp:
            cur = tmp.pop(0)
            result.append(cur.val)
            if cur.left:
                tmp.append(cur.left)
            if cur.right:
                tmp.append(cur.right)
        return result

二叉树中和为某一值得路径

题目

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

深度优先搜索。使用前序遍历，使用两个全局变量result和tmp，result来存放最终结果，tmp用来存放临时结果。

每次遍历，我们先把root的值压入tmp，然后判断当前root是否同时满足：

  • 与给定数值相减为0；
  • 左子树为空；
  • 右子树为空。

如果满足条件，就将tmp压入result中，否则，依次遍历左右子树。需要注意的是，遍历左右子树的时候，全局变量tmp是不清空的，直到到了根结点才请空tmp。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 not root.left and not root.right and root.val == expectNumber:
            return [[root.val]]
        
        # 递归向下寻找，直到找到叶子节点目标值
        left = self.FindPath(root.left, expectNumber-root.val)
        right = self.FindPath(root.right, expectNumber-root.val)
        res = [] 
        for i in left + right:
            res.append([root.val] + i) 
        return res

二叉树的深度

题目

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

思路

可以是递归的方法，属于DFS（深度优先搜索）；另一种方法是按照层次遍历，属于BFS（广度优先搜索）。

代码

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

平衡二叉树

题目

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

思路

重复遍历会影响算法的性能，所以很有必要掌握不需要重复遍历的方法。
如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。
只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶结点的路径的长度），
我们就可以一边遍历一边判断每个结点是不是平衡的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 1
        left = self.IsBalanced_Solution(pRoot.left)
        right = self.IsBalanced_Solution(pRoot.right)
        if not left:
            return False
        if not right:
            return False
        if abs(left-right) <= 1:
            return 1 + max(left,right)
        else:
            return False

二叉树的下一个节点

题目

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

思路

1结点有右子树: 那么它的下一个结点就是它的右子树的最左子结点。

也就是说从右子结点出发一直沿着指向左子树结点的指针，我们就能找到它的下一个结点。

例如，图中结点b的下一个结点是h，结点a的下一个结点是f。

2节点是左子节点: 接着我们分析一下结点没有右子树的情形。如果结点是它父结点的左子结点，

那么它的下一个结点就是它的父结点。例如，途中结点d的下一个结点是b，f的下一个结点是c。

3节点的父节点是左子节点: 如果一个结点既没有右子树，并且它还是父结点的右子结点，这种情形就比较复杂。

我们可以沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。

如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。

例如，为了找到结点g的下一个结点，我们沿着指向父结点的指针向上遍历，先到达结点c。

由于结点c是父结点a的右结点，我们继续向上遍历到达结点a。由于结点a是树的根结点。

它没有父结点。因此结点g没有下一个结点。

代码

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return pNode
        pNext = None
        # 如果当前节点有右子树，那么下一个节点就是右子树的最左节点
        if pNode.right is not None:
            pNode = pNode.right
            while pNode.left is not None:
                pNode = pNode.left
            pNext = pNode
        # 如果当前节点没有右子树，则需要找他的父节点
        elif pNode.next is not None:
            pParent = pNode.next
            while pParent is not None and pNode is pParent.right:
                pNode = pParent
                pParent = pNode.next
            pNext = pParent
        return pNext

对称的二叉树

题目

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

思路

1589704340351

我们通常有三种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这三种遍历算法中，都是先遍历左子结点再遍历右子结点。以前序遍历为例，我们可以定义一个遍历算法，先遍历右子结点再遍历左子结点，暂且称其为前序遍历的对称遍历。

遍历第一棵树，前序遍历的遍历序列为{8,6,5,7,6,7,5}，其对称遍历的遍历序列为{8,6,5,7,6,7,5}。

遍历第二颗树，前序遍历的遍历序列为{8,6,5,7,9,7,5}，其对称遍历的遍历序列为{8,9,5,7,6,7,5}。

可以看到，使用此方法可以区分前两棵树，第一棵树为对称树，第二颗树不是对称树。但是当使用此方法，你会发现第三颗树的前序遍历和对称前序遍历的遍历序列是一样的。

怎么区分第三颗树呢？解决办法就是我们也要考虑NULL指针。此时，前序遍历的遍历序列{7,7,7,NULL,NULL,7,NULL,NULL,7,7,NLL,NULL,NULL}，其对称遍历的遍历序列为{7,7,NULL,7,NULL,NULL,7,7,NULL,NULL,7,NULL,NULL}。因为两种遍历的序列不同，因此这棵树不是对称树。

代码

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        ## 判断左右子树是否互为镜像
        return self.recursiveTree(pRoot.left, pRoot.right)
    
    def recursiveTree(self, left, right):
        # 如果左右子树都是空树，则是镜像树
        if not left and not right:
            return True
        # 如果左右子树有一个为空，另一个不为空，那么不是镜像树
        if not left or not right:
            return False
        # 如果左右子树的根节点的数值不想等，不互为镜像树
        if left.val == right.val:
            # 递归判断左右自树是否是镜像树，注意左左比右右， 左右比右左
            return self.recursiveTree(left.left, right.right) and self.recursiveTree(left.right, right.left)
        return False

按之字的顺序打印二叉树

题目

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

思路

1589704378930

按之字顺序打印上图二叉树，打印顺序为：

1

3 2

4 5 6 7

15 14 13 12 12 10 9 8

为了达到这样打印的效果，我们需要使用两个栈。我们在打印某一行结点时，把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层（第一层、第三层等），则先保存左子树结点再保存右子树结点到第一个栈里。如果当前打印的是偶数层（第二层、第四层等），则则先保存右子树结点再保存左子树结点到第二个栈里。

代码

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    """docstring for Solution"""       
    def Print(self, pRoot):
        resultArray = []
        if not pRoot:
            return resultArray
        curLayerNodes = [pRoot]
        isEvenLayer = True
        while curLayerNodes:
            curLayerValues = []
            nextLayerNodes = []
            isEvenLayer = not isEvenLayer
            for node in curLayerNodes:
                curLayerValues.append(node.val)
                if node.left:
                    nextLayerNodes.append(node.left)
                if node.right:
                    nextLayerNodes.append(node.right)
            curLayerNodes = nextLayerNodes
            resultArray.append(curLayerValues[::-1]) if isEvenLayer else resultArray.append(curLayerValues)
        return resultArray

把二叉树打印成多行

题目

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

思路

使用队列即可

代码

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
# 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 []
        
        result = []
        curStack = [pRoot]
        
        while curStack:
            tmpStack = list()
            tmpResult = list()
            for node in curStack:
                tmpResult.append(node.val)
                if node.left:
                    tmpStack.append(node.left)
                if node.right:
                    tmpStack.append(node.right)
            curStack = tmpStack
            result.append(tmpResult)
        return result

序列化二叉树

题目

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

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

思路

使用前序遍历来序列化和发序列化即可。只要自己写的程序格式对应上即可。可以使用$符号表示NULL，同时每个结点之间，需要添加逗号，即’,’进行分隔。

代码

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
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    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
        list = s.split(",")
        return self.deserializeTree(list)
    def deserializeTree(self, list):
        if len(list)<=0:
            return None
        val = list.pop(0)
        root = None
        if val != '#':
            root = TreeNode(int(val))
            root.left = self.deserializeTree(list)
            root.right = self.deserializeTree(list)
        return root
刘小恺(Kyle) wechat
如有疑问可联系博主