《剑指Offer》树

1 基础知识

树的操作会涉及到大量指针，因此与树有关的面试题都不太容易。当面试官想考察应聘者在有复杂指针操作的情况下写代码的能力时，他往往会想到用与树有关的面试题。

面试时提到的树，大部分是二叉树。二叉树最重要的操作是遍历，遍历有三种方法：

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

这3种遍历都有递归和循环两种不同的实现方法。

二叉树有很多特例，例如二叉搜索树。二叉搜索树中，左子节点总是小于或等于根节点，而右子节点总是大于或等于根节点。在二叉搜索树中，可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个节点。

二叉树的另外两个特例是堆和红黑树。

• 堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。
• 红黑树是把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。

需要注意的是，二叉树的两棵子树有着明确的左右之分，讨论子树时必须明确说明是左子树还是右子树。

二叉树的多种形态

相关概念：

• 路径：从祖先节点到其任意子孙节点的一系列首尾相连的边称为树中的一条路径
• 层：规定二叉树根的层数为0。从树根到树中任一节点的路径长度就是该节点所在的层数，也称为该节点的层数。
• 深度（也叫高度）：一颗二叉树的高度是树中节点的最大层数。树的高度是二叉树的整体性质。只有根节点的树高度为0，人们一般不讨论空树的高度。

二叉树的性质：

• 在非空二叉树第i层中之多有2^i个节点
• 高度为h的二叉树至多有2^(h+1)-1个节点

2 二叉树的Python实现

简单来看，二叉树节点是一个三元祖，元素是左右子树和本节点数据。Python的list或者tuple都可以用于组合这样的三个元素，两者的差异仅在于变动性。下面讨论用list构造二叉树。

二叉树是递归结构，Python的list也是递归结构。可以采用下面的设计：

• 空树用None表示
• 非空二叉树用包含3个元素的表 [d, l, r]表示，例如：
  ['A', ['B', None, None], 'C' ]

3 面试题

3.1 重建二叉树

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

Python solution：
运行时间：53ms, 占用内存：5732k

# 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 not pre or not tin:
            return None
        root = TreeNode(pre.pop(0))
        index = tin.index(root.val)
        root.left = self.reConstructBinaryTree(pre,tin[:index])
        root.right = self.reConstructBinaryTree(pre,tin[index+1:])
        return root

3.2 二叉树的下一个节点

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

Python实现：
运行时间：27ms, 占用内存：5856k

# -*- 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 pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        while pNode.next:
            if(pNode.next.left == pNode):
                return pNode.next
            pNode = pNode.next
        return