数据结构经典面试题-树

作者: arrnos | 来源:发表于2019-08-03 14:02 被阅读0次

Golang 实现 Trie (前缀树) leetcode-20
数据结构经典面试题-树
面试：原来Redis的五种数据类型数底层结构是这样的
iOS经典面试题总结--内存管理
面试材料
Python实现二叉树常规面试题
链表反转
Android 面试题(重点2)
经典面试100题 - 持续更新中
数据结构 - 概要

本系列针对面试中【经典】算法题进行分类和汇总，每篇包含两部分：基础知识和经典题目。

本文的主角是【树】。

本文结构：

面试前必须知道的[树]的基础知识。
[树]的经典手写编程题。

基础知识

基础概念

img

基础性质

img

经典面试题

二叉树以及二叉搜索树初始化

class Node():
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Tree():
    def __init__(self):
        self.root = None

    def rand_tree(self, x): #普通二叉树构建
        node = Node(x)
        if not self.root:
            self.root = node
            return
        temp = [self.root]
        while True:
            p = temp.pop(0)
            if not p.left:
                p.left = node 
                return
            elif not p.right:
                p.right = node 
                return 
            temp.append(p.left)
            temp.append(p.right)

    def sort_tree(self, x): #搜索二叉树构建
        node = Node(x)
        if not self.root:
            self.root = node
            return 
        p = self.root
        while True:
            if x<p.val:
                if not p.left:
                    p.left = node 
                    return 
                p = p.left
            elif x>=p.val:
                if not p.right:
                    p.right = node
                    return
                p = p.right

层次遍历

def traverse(root):
    if not root:
        return
    temp = [root]
    res = []
    while temp:
        p = temp.pop(0)
        res.append(p.val)
        if p.left:
            temp.append(p.left)
        if p.right:
            temp.append(p.right)
    return res

前序遍历

#递归版
def preoder_recursion(root):
    if not root:
        return []
    left = preoder_recursion(root.left)
    res = [root.val]
    right = preoder_recursion(root.right)
    return res+left+right

#非递归版
def preorder(root):
    if not root:
        return
    res = []
    temp = [root]
    while temp:
        while temp[-1]:
            res.append(temp[-1].val)
            temp.append(temp[-1].left)
        temp.pop()
        if temp:
            p = temp.pop()
            temp.append(p.right)
    return res

中序遍历

#递归版
def inorder_recursion(root):
    if not root:
        return []
    left = inorder_recursion(root.left)
    res = [root.val]
    right = inorder_recursion(root.right)
    return left+res+right   

#非递归
def inorder(root):
    if not root:
        return 
    res = []
    temp = [root]
    while temp:
        while temp[-1]:
            temp.append(temp[-1].left)
        temp.pop()
        if temp:
            p = temp.pop()
            res.append(p.val)
            temp.append(p.right)
    return res

后续遍历

#递归版
def postorder_recursion(root):
    if not root:
        return []
    left = postorder_recursion(root.left)
    res = [root.val]
    right = postorder_recursion(root.right)
    return left+right+res 

#非递归版
def postorder(root):
    if not root:
        return
    res = []
    temp = [root]
    while temp:
        while temp[-1]:
            p = temp[-1]
            if p.right:
                temp.append(None)  #用None作为分隔
                temp.append(p.right)
            else:
                temp.append(p.right)
            temp.append(p.left)
        temp.pop()
        if temp:
            if not temp[-1]:
                temp.pop()
                res.append(temp.pop().val)
            else:
                res.append(temp.pop().val)
    return res

重建二叉树

pre = [3,0,1,2,6,5,4,8,7,9]
mid = [0,1,2,3,4,5,6,7,8,9]
pos = [2,1,0,4,5,7,9,8,6,3]
要求不含重复数字，对于根据后序和前序遍历重建二叉树要求二叉树是搜索二叉树，不然结构不确定。

#根据前序和中序遍历
def reconstruct_1(pre, mid):
    if len(pre)==0:
        return None
    elif len(pre)==1:
        return Node(pre[0])
    root = mid.index(pre[0])
    flag = Node(pre[0])
    flag.left = reconstruct_1(pre[1:root+1], mid[:root])
    flag.right = reconstruct_1(pre[root+1:], mid[root+1:])
    return flag

#根据后序和中序遍历
def reconstruct_2(pos, mid):
    if len(pos)==0:
        return None
    elif len(pos)==1:
        return Node(pos[0])
    root = mid.index(pos[-1])
    flag = Node(pos[-1])
    flag.left = reconstruct_2(pos[:root], mid[:root])
    flag.right = reconstruct_2(pos[root:-1], mid[root+1:])
    return flag

#根据前序和后序遍历
def reconstruct_3(pre, pos):
    print(pre)
    print(pos)
    if len(pos)==0:
        return None
    elif len(pos)==1:
        return Node(pos[0])
    index = pos.index(pre[1])
    flag = Node(pre[0])
    if index==len(pos)-2:
        if flag.val<pos[0]: #判断应该在左子树还是右子树，所以要求是二叉搜索树
            flag.right = reconstruct_3(pre[1:], pos[:-1])
        else:
            flag.left = reconstruct_3(pre[1:], pos[:-1])
    else:
        flag.left = reconstruct_3(pre[1:index+2], pos[:index+1])
        flag.right = reconstruct_3(pre[index+2:], pos[index+1:-1])
    return flag

树的子结构

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

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, 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)

二叉树的镜像

将给定的二叉树变换为其镜像。

class Solution():
    def Mirror(self, root):
        if not root:
            return 
        if not root.left and not root.right:
            return 
        root.left, root.right = root.right, root.left
        self.Mirror(root.left)
        self.Mirror(root.right)
        return root

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

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

class Solution():
    def FindPath(self, root, expectNumber):
        if not root:
            return []
        if 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

二叉搜索树与双向链表

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

class Solution:
    def __init__(self):
        self.listHead = None
        self.listTail = None
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return
        self.Convert(pRootOfTree.left)
        if not self.listHead:
            self.listHead = pRootOfTree
            self.listTail = pRootOfTree
        else:
            self.listTail.right = pRootOfTree
            pRootOfTree.left = self.listTail
            self.listTail = pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.listHead

二叉树的深度

#递归版
class Solution():
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return left+1 if left>right else right+1

#循环版
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        p = [pRoot]
        last = p[-1]
        layer = 0
        while p:
            p1 = p.pop(0)
            if p1.left:
                p.append(p1.left)
            if p1.right:
                p.append(p1.right)
            if p1==last:
                layer += 1
                if p:
                    last = p[-1]
        return layer

平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1，那么它就是平衡二叉树。

class Solution:
    def IsBalanced_Solution(self, pRoot):
        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
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return max(left+1, right+1)

二叉树的下一个结点

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

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:
            p = pNode.right
            while p.left:
                p = p.left
            return p 
        else:
            while pNode.next:
                if pNode.next.left==pNode:
                    return pNode.next
                pNode = pNode.next 
        return None

对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
（1）如果左右子树有一个为空，那么该二叉树肯定不是对称二叉树
（2）如果左右子树均不为空，但是节点的值不同，那么该二叉树肯定不是对称二叉树

class Solution:
#对称比较方法，其实也就是前序和镜像前序遍历比较的方法，和下面的对称遍历方法一个意思
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
            return False
        return self.iSame(pRoot.left, pRoot.right)
    def iSame(self, p1, p2):
        if not p1 and not p2:
            return True
        if not p1 or not p2 or (p1.val!=p2.val):
            return False
        return self.iSame(p1.left, p2.right) and self.iSame(p1.right, p2.left)

#对称遍历方法（先存储后比较）
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        if (pRoot.left and not pRoot.right) or (pRoot.right and not pRoot.left):
            return False
        return self.preorder(pRoot) == self.preorder_n(pRoot)

    def preorder(self, pRoot):
        if not pRoot:
            return [None]
        left = self.preorder(pRoot.left)
        right = self.preorder(pRoot.right)
        return [pRoot.val]+left+right

    def preorder_n(self, pRoot):
        if not pRoot:
            return [None]      
        left = self.preorder_n(pRoot.left)    
        right = self.preorder_n(pRoot.right)    
        return [pRoot.val]+right+left

按之字形顺序打印二叉树

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

class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        res = []
        res_1 = []
        temp = [pRoot]
        left_to_right = 1
        last = temp[-1]
        while temp:
            p = temp.pop(0)
            res_1.append(p.val)
            if p.left:
                temp.append(p.left)
            if p.right:
                temp.append(p.right)
            if p==last:
                res.append(res_1 if left_to_right else res_1[::-1])
                left_to_right = not left_to_right
                res_1 = []
                if temp:
                    last = temp[-1]
        return res

序列化二叉树

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

class Solution:
    def Serialize(self, root):
        if not root:
            return '#,'
        s = str(root.val) + ','
        left = self.Serialize(root.left)
        right = self.Serialize(root.right)
        s += left + right
        return s 

    def Deserialize(self, s):
        list1 = s.split(',')
        return self.deserializeTree(list1)

    def deserializeTree(self, list1):
        if len(list1)<=0:
            return None
        val = list1.pop(0)
        root = None # 每次递归需要初始化，不然程序不知道是全局变量还是局部变量
        if val != '#':
            root = Node(int(val))
            root.left = self.deserializeTree(list1)
            root.right = self.deserializeTree(list1)
        return root

二叉搜索树的第k个结点

class Solution:
    def KthNode(self, pRoot, k):
        if not pRoot:
            return None
        temp = [pRoot]
        res = []
        while temp:
            while temp[-1]:
                temp.append(temp[-1].left)
            temp.pop()
            if temp:
                p = temp.pop()
                res.append(p)
                temp.append(p.right)
                if len(res)==k:
                    return res[-1]

更多干货，持续发送

Golang 实现 Trie (前缀树) leetcode-20
前缀树，字典树，经典的数据结构。
数据结构经典面试题-树
本系列针对面试中【经典】算法题进行分类和汇总，每篇包含两部分：基础知识和经典题目。本文的主角是【树】。本文结构...
面试：原来Redis的五种数据类型数底层结构是这样的
关注我，可以获取最新知识、经典面试题以及微服务技术分享在Redis中会涉及很多数据结构，比如SDS，双向链表...
iOS经典面试题总结--内存管理
iOS经典面试题总结--内存管理 iOS经典面试题总结--内存管理
面试材料
面试经验面试题1 面试题2 面试题3 面试题4 面试题5 面试题6――数据结构面试题7――网络面试题8――汇...
Python实现二叉树常规面试题
以前只是零散的学习了二叉树这种数据结构，下面总结下二叉树相关面试题的Python实现。后续会补充
链表反转
概述链表反转是非常经典的面试题，要实现此功能，需先实现链表的数据结构。链表类获得单向链表方法输出单向链表方...
Android 面试题(重点2)
掘金官网Android面试题 Android 动画 Android 动画Android面试题算法和数据结构设计...
经典面试100题 - 持续更新中
打算整理100道经典面试题，整理出来的链接都会附录在下面。经典面试题1：图片占多少内存经典面试题2：时针和分针经...
数据结构 - 概要
数组链表堆/栈/队列树数据结构 - 二叉树数据结构 - 二叉查找树数据结构 - 平衡二叉树数据结构 - A...