目录

二叉树

1、重建二叉树

2、树的子结构

3、二叉树的镜像

4、从上往下打印二叉树

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

6、二叉树的深度

7、二叉树的下一个结点

8、对称的二叉树

9、把二叉树打印成多行

10、按之字形顺序打印二叉树

11、序列化二叉树

12、平衡二叉树

13、二叉搜索树的后序遍历

14、二叉搜索树与双向链表

15、二叉搜索树的第k个结点

---

二叉树

1、重建二叉树

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

思路：

# -*- 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):
        # write code here
        #判断pre或tin是否为空，为空就返回None
        if not pre or not tin:
            return None
        #因为pre为先序遍历，pre中的第一个点为首节点
        root=TreeNode(pre[0])
        #找到首节点在中序遍历中的索引位置
        pos=tin.index(pre[0])
        #对左右分别递归
        root.left=self.reConstructBinaryTree(pre[1:pos+1],tin[0:pos])
        root.right=self.reConstructBinaryTree(pre[pos+1:],tin[pos+1:])
        return root

2、树的子结构

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

思路：考虑到使用递归完成，一个函数嵌套递归判断是否匹配到起始节点；另写一个递归，判断左子树和右子树是否为子结构的函数。

（1） 判断A当前节点开始，B是否为子结构，如果不是看下A的左子树节点，如果也不是再看下A的右子树。

（2）如果是某节点开始A与B的起始节点重合：①判断B是否匹配完了，如果匹配完了说明为子结构；②如果A匹配完了，或者A的值和B和值不等，直接返回False；③如果当前点相同，那同时看一下左子树和右子树的情况；

# -*- 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
        result=False
        if pRoot1.val==pRoot2.val:
            result=self.IsSubtree(pRoot1,pRoot2)
        if not result:
            result=self.IsSubtree(pRoot1.left,pRoot2)
        if not result:
            result=self.IsSubtree(pRoot1.right,pRoot2)
        return result
    def IsSubtree(self,p1,p2):
        if not p2:
            return True
        if not p1 or p1.val!=p2.val:
            return False
        return self.IsSubtree(p1.left,p2.left) and self.IsSubtree(p1.right,p2.right)
    

3、二叉树的镜像

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

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

思路：

# -*- coding:utf-8 -*-
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.right=root.right,root.left
        self.Mirror(root.left)
        self.Mirror(root.right)

4、从上往下打印二叉树

问题：从上往下打印出二叉树的每个节点，同层节点从左至右打印。（相当于层次遍历）

思路：利用队列的先进先出(FIFO)特性解决。每从队列头部获取一个节点，就将该节点的左右子节点存入队列的尾部。如此往复，直至队列为空。

?

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        result=[]
        arr=[]    #使用arr数组存储要打印的节点
        arr.append(root)
        while arr:
            currentRoot=arr.pop(0)
            result.append(currentRoot.val)
            if currentRoot.left!=None:
                arr.append(currentRoot.left)
            if currentRoot.right!=None:
                arr.append(currentRoot.right)
        return result

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

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

思路：

# -*- 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 not root.left and not root.right and expectNumber==root.val:
            return[[root.val]]
        result=[]
        #如果不是叶子节点，分别对根节点的左子树、右子树进行递归
        left=self.FindPath(root.left,expectNumber-root.val)
        right=self.FindPath(root.right,expectNumber-root.val)
        for i in left+right:
            result.append([root.val]+i)
        return result

6、二叉树的深度

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

思路一：递归

# -*- 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
        left=self.TreeDepth(pRoot.left)
        right=self.TreeDepth(pRoot.right)
        return max(left+1,right+1)

思路二：非递归，层次遍历

# -*- 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
        curLevelNodeList=[pRoot]
        length=0
        while curLevelNodeList:
            tempNodeList=[]
            for node in curLevelNodeList:
                if node.left:
                    tempNodeList.append(node.left)
                if node.right:
                    tempNodeList.append(node.right)
            curLevelNodeList=tempNodeList
            length+=1
        return length

7、二叉树的下一个结点

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

思路：

（1） 若该节点存在右?树：则下?个节点为右?树最左?节点（如图节点B）

（2）若该节点不存在右?树：这时分两种情况：

第一种： 该节点为父节点的左?节点，则下?个节点为其父节点（如图节点D）

第二种：该节点为父节点的右?节点，则沿着?节点向上遍历，直到找到?个节点是其父节点的左?节点，则该节点的?节点是下?个节点（如图节点I，沿着父节点?直向上查找找到B（B为其?节点的左?节点），则B的父节点A为下?个节点）

# -*- 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):
        if not pNode:
            return None
        #判断当前结点有没有右子树，若存在右子树，下一个结点就是右子树的最左子结点
        if pNode.right:
            pNode=pNode.right  #进入到右子树的父节点
            while pNode.left:  #不断遍历左子树
                pNode=pNode.left
            return pNode   #返回右子树的最左子结点
        #没有右子树就向上遍历找到他的父节点，如果它是父节点的左孩子结点，下一个结点就是父节点
        #如果不是，就继续向上寻找当前父节点w的父节点q，并判断q是否为他的父节点e左孩子
        #如此反复直到找到匹配的情况，找不到就返回None
        while pNode.next:
            if pNode.next.left==pNode:
                return pNode.next
            else:
                pNode=pNode.next
        return None

8、对称的二叉树

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

思路：

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        return self.judge_helper(pRoot.left,pRoot.right)

    def judge_helper(self,left,right):
        if not left and not right:  #当left和right都为空时，返回True
            return True
        if not left or not right:   #当left和right有一边为空时，返回False
            return False
        # 判断left和right的val是否相等，相等就继续递归判断应该对称的两个点是否对称
        if left.val==right.val:
            return self.judge_helper(left.left,right.right) and self.judge_helper(left.right,right.left)
        return False

9、把二叉树打印成多行

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

思路：

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        resultList=[]
        curLayer=[pRoot]
        while curLayer:
            curList=[]
            nextLayer=[]
            for node in curLayer:
                curList.append(node.val)
                if node.left:
                    nextLayer.append(node.left)
                if node.right:
                    nextLayer.append(node.right)
            curLayer=nextLayer
            resultList.append(curList)
        return resultList

10、按之字形顺序打印二叉树

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

思路：按顺序获取每一层节点的值；将偶数层节点的值倒序。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        resultList=[]
        curLayer=[pRoot]
        isEvenLayer=True  #增加标志变量，初始化为从右向左
        while curLayer:
            curList=[]
            nextLayer=[]
            isEvenLayer=not isEvenLayer
            for node in curLayer:
                curList.append(node.val)
                if node.left:
                    nextLayer.append(node.left)
                if node.right:
                    nextLayer.append(node.right)
            curLayer=nextLayer
            if isEvenLayer:
                resultList.append(curList[::-1])
            else:
                resultList.append(curList)
        return resultList

11、序列化二叉树

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

思路：（1）序列化二叉树：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、按层 的二叉树遍历方式，序列化时通过某种符号表示空节点（’#‘），序列化的结果是一个字符串，字符串之间用“，”隔开。（采用先序遍历的方式实现）

（2）反序列化二叉树：根据某种遍历顺序得到的序列化字符串，重构二叉树。（按先序遍历重构）

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Serialize(self, root):
        if not root:
            return '#'
        return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)

    def Deserialize(self, s):
        s_list=s.split(',')
        return self.deserializeTree(s_list)
    def deserializeTree(self,list):
        if len(list)<=0:
            return None
        data=list.pop(0)
        root=None
        if data!='#':
            root=TreeNode(int(data))
            root.left=self.deserializeTree(list)
            root.right=self.deserializeTree(list)
        return root

12、平衡二叉树

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

思路：

# -*- 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):
        if not pRoot:
            return True
        #对左右两边同时递归
        if abs(self.Tree_depth(pRoot.left)-self.Tree_depth(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

    def Tree_depth(self,pRoot):
        if not pRoot:
            return 0
        #二叉树的后续遍历
        left=self.Tree_depth(pRoot.left)
        right=self.Tree_depth(pRoot.right)
        return max(left+1,right+1)

13、二叉搜索树的后序遍历

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

思路：递归思想。把数组分成三部分，比如[4,8,6,12,16,14,10]，10就是根节点，4,8,6都是左子树，12,16,14,10都是右子树，然后针对左右子树再去判断是不是符合根节点、左右子树这一个规律（左子树都比根节点小，右子树都比根节点大）。

?

?

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence)==0:
            return False
        root=sequence[-1]  #后续遍历中，root是sequence最后一个结点
        index=0
        #根据二叉搜索树左子树小于root值，找到第一个大于root的index，即为左右子树划分索引
        for i in range(len(sequence)-1):
            index+=1
            if sequence[i]>root:
                break
        #二叉搜索树右子树大于root值
        for j in range(index,len(sequence)-1):
            if sequence[j]<root:
                return False
        #判断左子树是不是二叉搜索树
        left_yes_or_no=True
        left=sequence[:index]
        if left:
            left_yes_or_no=self.VerifySquenceOfBST(left)
        #判断右子树是不是二叉搜索树
        right_yes_or_no=True
        right=sequence[index:len(sequence)-1]
        if right:
            right_yes_or_no=self.VerifySquenceOfBST(right)
        return left_yes_or_no and right_yes_or_no
        

14、二叉搜索树与双向链表

问题：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：

首先，在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点；

其次，由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每?个结点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每?一个结点；

最后，按照中序遍历的顺序，当我们遍历转换到根结点（值为10的结点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，此时链表中的最后一个结点就是10了，接着我们去遍历转换右子树，并把根结点和右子树中最小的结点链接起来。

很明显，转换它的左子树和右子树，由于遍历和转换过程是一样的，很自然地想到可以用递归。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return
        self.head=self.pre=None
        self.InOrder(pRootOfTree)
        return self.head

    def InOrder(self,root):
        if not root:
            return
        self.InOrder(root.left)
        if not self.head:
            self.head=self.pre=root
        else:
            self.pre.right=root
            root.left=self.pre
            self.pre=root
        self.InOrder(root.right)

15、二叉搜索树的第k个结点

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

思路：遇到二叉搜索树（BST）想中序遍历。这个题先中序遍历，然后找出第k个结点。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def KthNode(self, pRoot, k):
        self.result=[]
        self.InOrder(pRoot)
        if k<=0 or len(self.result)<k:
            return None
        return self.result[k-1]   #返回中序遍历第k个即为第k小的结点

    def InOrder(self,root):
        if not root:
            return
        if root.left:
            self.InOrder(root.left)
        self.result.append(root)   #中序遍历所有结点，加入到result中
        if root.right:
            self.InOrder(root.right)

?

cs