牛客网习题集——剑指offer面试题第六部分（二叉树的各种遍历，堆的用法）

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

# -*- 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:
            pRoot = pNode.next
            if pRoot.left == pNode:
                return pRoot
            pNode = pNode.next
 #找规律，分三种情况讨论（评论区）

评论区思路：

链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
来源：牛客网：首先知道中序遍历的规则是：左根右，然后作图

结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
//分析二叉树的下一个节点，一共有以下情况：
//1.二叉树为空，则返回空；
//2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
//3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。
classSolution{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if (pNode == NULL)
            returnNULL;
        if (pNode->right != NULL)
        {
            pNode = pNode->right;
            while (pNode->left != NULL)
                pNode = pNode->left;
            returnpNode;
        }
        while (pNode->next != NULL)
        {
            TreeLinkNode *proot = pNode->next;
            if (proot->left == pNode)
                returnproot;
            pNode = pNode->next;
        }
        returnNULL;
    }
};

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

# -*- 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
        if not pRoot:
            return True
        return  self.compare(pRoot.left,pRoot.right)
    def compare(self,left,right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val == right.val:
            if self.compare(left.left,right.right) and self.compare(left.left,right.right):
                return True #上一行很重要，要在代码中体现对称
        return False

 考察递归

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

# -*- 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 = []      # 
        stack = [] #利用栈实现
        stack.append(pRoot)
        while stack:
            res = []   #储存下一行的值
            nextstack = [] #储存下一行的结点
            for i in stack: #遍历完这一行，包括添加结点与值
                res.append(i.val)
                if i.left:
                    nextstack.append(i.left)
                if i.right:
                    nextstack.append(i.right)
            stack = nextstack
            result.append(res)
        for i in range(len(result)): 偶数行要反转
            if i%2 == 1:
                result[i].reverse()
        return result
    '''大佬代码：链接：https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
来源：牛客网

class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        nodeStack=[pRoot]
        result=[]
        while nodeStack:
            res = []
            nextStack=[]
            for i in nodeStack:
                res.append(i.val)
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
            nodeStack=nextStack
            result.append(res)
        returnResult=[]
        for i,v in enumerate(result):
            if i%2==0:
                returnResult.append(v)
            else:
                returnResult.append(v[::-1])
        return returnResult

用一个队列存储，然后记得偶数行要反转（第一行k=0）

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

# -*- 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 []
        result = []
        queue = [pRoot]
        while queue:
            res = []
            nextqueue = []
            for i in queue:
                res.append(i.val) #是小括号！！
                if i.left:
                    nextqueue.append(i.left)
                if i.right:
                    nextqueue.append(i.right)
            result.append(res)
            queue = nextqueue
        return result

思路一样，注意输出的格式。（为空时也要注意输出格式）

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

# -*- 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
        self.res = []
        res1 = ''
        if not root:
            return '#,'
        self.mid(root)
        res1 = ','.join(self.res)
        return res1
    def mid(self,root): #前序遍历
        if not root:
            self.res.append('#')
            return
        self.res.append(str(root.val))
        self.mid(root.left)
        self.mid(root.right)
    def Deserialize(self, s):
        # write code here
        self.flag += 1
        l = s.split(',')
        root = None
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root
                          
 #前序遍历可以直接找到根节点
     

考察前序遍历，递归法比较好做。注意join的用法，后面List必须是str才能连接。

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

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode 
    #python解法，要注意，返回的是节点，而不是节点的值！！！尼玛，被坑了。!!!
    def KthNode(self, pRoot, k):
        # write code here
        if not k:
            return None
        self.res = []  #牢记self
        self.mid(pRoot)
        if k > len(self.res) or k < 0: #k的越界判断
            return None
        return self.res[k-1]
    def mid(self,root):  #递归实现
        if not root:
            return None
        self.mid(root.left)
        self.res.append(root)
        self.mid(root.right)
           

先递归实现中序遍历再返回指定的值即可，一定要注意的是，本题要求返回的是结点（root) 而不是结点的值（root.val)!!!root.val)!!!

7 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

class Solution:
    def __init__(self):
        self.arr=[]
    def Insert(self, num):
        self.arr.append(num)
        self.arr.sort()
    def GetMedian(self,***):
        length=len(self.arr)
        return self.arr[length//2] if length%2==1 else (self.arr[length//2]+self.arr[length//2-1])/2.0
#注意self 学到的知识点
'''1、在python类中定义类变量时，
在__init__()函数中，通过self.variable_name 
定义
2、整数除以整数的结果为整数，如果想得到相除结果为
浮点数，则需要除以浮点数
self.l[length//2] + self.l[length//2 -1]) / 2
转换为
self.l[length//2] + self.l[length//2 -1]) / 2.0
--------------------- 
作者：cchangcs 
来源：CSDN 
原文：https://blog.csdn.net/github_39611196/article/details/88919102 
版权声明：本文为博主原创文章，转载请附上博文链接！'''

暴力法，注意要有self!

知识补充： 

1 数据流的中位数，可以用堆解决：

链接：https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
来源：牛客网

插入有两种思路：

     * 1：直接插入大堆中，之后若两堆尺寸之差大于1(也就是2)，则从大堆中弹出堆顶元素并插入到小堆中

     * 若两队之差不大于1，则直接插入大堆中即可。

     * 2：奇数个数插入到大堆中，偶数个数插入到小堆中，

     * 但是 可能会出现当前待插入的数比小堆堆顶元素大，此时需要将元素先插入到小堆，然后将小堆堆顶元素弹出并插入到大堆中

     * 对于偶数时插入小堆的情况，一样的道理。why?

     * 因为要保证最大堆的元素要比最小堆的元素都要小。

https://blog.csdn.net/u010005281/article/details/80327328 用堆解

2 python 中的堆 原理：https://www.cnblogs.com/kumata/p/9201571.html 用法：https://blog.csdn.net/u013206202/article/details/78968438

3 二叉搜索树的定义 https://blog.csdn.net/u013405574/article/details/51058133

4 中序遍历图解 https://blog.csdn.net/qq_33243189/article/details/80222629

5 三种遍历精讲 https://segmentfault.com/a/1190000016674584  python实现三种遍历 https://www.cnblogs.com/icekx/p/9127569.html

6 python中自带的栈与队列 https://www.cnblogs.com/yupeng/p/3413852.html

7 join方法文档 https://www.runoob.com/python/att-string-join.html

8 enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。>>>seq = ['one', 'two', 'three']

>>> for i, element in enumerate(seq):

... print i, element

0  one

1 two

2 three