《剑指 Offer》中树的基础部分

数据结构

引言

数据结构一直是面试的重点，大多数会围绕着数组、字符串、链表、树、栈、队列等几种常见的数据结构展开，因此我们需要熟练掌握这几种数据结构。
数组和字符串是两种最为基础的数据结构，它们利用连续的内存存放数字和字符。而链表和树则是面试频率相对较高的数据结构。由于操作链表和树时需要操作相当数量的指针，因此在解决相关问题时，要特别重视相应的鲁棒性，否则容易出现程序崩溃的问题。栈与递归密切相关，而队列也和 BFS（广度优先遍历算法）密切相关，深刻理解这几种数据结构可以帮助我们解决很多问题。

数组

参照《剑指 offer》笔记一

字符串和链表

参照《剑指 offer》笔记二

树

基础概念

树是一种在实际编程中经常遇到的数据结构。它的逻辑很简单：除了根节点之外，每个节点只有一个父节点，根节点没有父节点；除了叶节点外的所有节点都有一个或多个子节点，叶节点没有子节点。父节点和子节点之间利用指针连接。由于树的操作会涉及到大量的指针，因此和树相关的题目都相对复杂。
一般我们提到的树，大多数是二叉树。所谓二叉树，是树的一种特殊结构：每个节点最多只能有两个子节点。在二叉树中最重要的操作莫过于是遍历，即按照某一顺序访问树中的所有节点。通常存在以下三种遍历方式：

前序遍历：先访问根节点，再访问左子节点，最后访问右子节点。
中序遍历：先访问左子节点，再访问根节点，最后访问右子节点。
后序遍历：先访问左子节点，再访问右子节点，最后访问根节点。
例如，下列二叉树：
1
2
3
4
5
    10
   /  \
  6    14
 / \   / \
4   8 12  16

查看遍历结果

它的遍历如下：
前序遍历：10 6 4 8 14 12 16
中序遍历：4 6 8 10 12 14 16
后序遍历：4 8 6 12 16 14 10

这三种遍历都有递归/循环两种不同的实现方法，每种遍历的递归实现都比循环实现简洁许多。此外，我们还有另外两种的遍历方式：

深度优先搜素

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

广度优先搜素

广度优先搜索算法（英语：Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

二叉树有许多的特例，例如二叉搜索树。在二叉搜索树中，左子节点总是小于等于根节点，右子节点总是大于等于根节点。我们可以在平均$O(logn)$的时间内根据数值在二叉搜索树中找到一个节点。
另外的两个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中，根节点值最大，最小堆中根节点值最小。许多需要快速查找最大值/最小值的问题都可以用堆来解决。
而红黑树则是把树中的节点分为红、黑两种颜色，并通过规则确保根节点到叶节点的最长路径长度不超过最短路径的两倍。在C++的STL中，set、multiset、map、multimap等数据结构都是基于红黑树来实现的。红黑树的实现则相对复杂。~~儿子 4 岁了还不会手写红黑树，怎么办？~~

题目分析

题目一

下面我们来看一道例题：

题目：输入某二叉树的前序遍历和中序遍历结果，重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复数字。二叉树的节点定义如下：
1
2
3
4
5
struct BinaryTreeNode{
    int                 m_nValue;
    BinaryTreeNode*     m_pLeft;
    BinaryTreeNode*     m_pRight;
};

广度优先搜素

前序遍历的第一个数字是根结点的值，而扫描中序遍历序列可以确定根结点的值的位置。也即是可以划分左右子树。那么我们对于左右子树也可以通过递归的方式来构建他们。

示例代码

BinaryTreeNode *construct(int *preOrder, int *inOrder, int length) {
    if (preOrder == nullptr || inOrder == nullptr || length <= 0) {
        return nullptr;
    }
    return constructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}

BinaryTreeNode *constructCore(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder) {

    // The first value in preOrder is the value of root

    int rootValue = startPreorder[0];
    auto *root = new BinaryTreeNode();
    root->m_nValue = rootValue;
    root->m_pLeft = root->m_pRight = nullptr;

    if (startPreorder == endPreorder) {
        if (startInorder == endInorder && *startPreorder == *startInorder) {
            return root;
        } else {
            throw std::runtime_error("Invalid input.");
        }
    }

    int *rootInorder = startInorder;
    while (rootInorder <= endInorder && *rootInorder != rootValue) {
        ++rootInorder;
    }

    if (rootInorder == endInorder && *rootInorder != rootValue) {
        throw std::runtime_error("Invalid input");
    }

    int leftLength = rootInorder - startInorder;
    int *leftPreorderEnd = startPreorder + leftLength;

    if (leftLength > 0) {
        // Build the left subtree
        root->m_pLeft = constructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
    }

    if (leftLength < endPreorder - startPreorder) {
        root->m_pRight = constructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
    }

    return root;
}

在函数constructCore中，我们先根据前序遍历的第一个数字创建根节点，接下来在中序遍历序列中找到根节点的位置，这样就能够确定左右子树节点的数量。在前序遍历和中序遍历序列中划分了左、右子树节点的值后，我们就可以递归地调用函数constructCore去分别构建它的左右子树。

课后习题

给定一科二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针外，还有一个指向父节点的指针。
1
2
3
4
5
6
struct BinaryTreeNode {
    int m_nValue;
    BinaryTreeNodet *m_pLeft;
    BinaryTreeNode *m_pRight;
    BinaryTreeNode *m_pParent;
};

解题思路

如果一个节点有右子树，那么它的下一个节点就是它的右子树的最左节点。也就是说，从右节点出发一直沿着指向左子节点的指针，我们就能找到它的下一个节点。
如果一个节点没有右子树。分情况考虑：如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。
如果一个节点既没有右子树，并且它还是它父节点的右子节点。我们可以沿着父节点指针一直向上遍历，直到找到一个它父节点的左子节点的节点。如果存在，则是我们要寻找的下一个节点。

示例代码

BinaryTreeNode *getNext(BinaryTreeNode *pNode) {
    if (pNode == nullptr) {
        return nullptr;
    }
    BinaryTreeNode *pNext = nullptr;
    if (pNode->m_pRight != nullptr) {
        BinaryTreeNode *pRight = pNode->m_pRight;
        while (pRight->m_pLeft != nullptr) {
            pRight = pRight->m_pLeft;
        }
        pNext = pRight;
    } else if (pNode->m_pParent != nullptr) {
        BinaryTreeNode *pCurrent = pNode;
        BinaryTreeNode *pParent = pNode->m_pParent;
        while (pParent != nullptr && pCurrent == pParent->m_pRight) {
            pCurrent = pParent;
            pParent = pParent->m_pParent;
        }
        pNext = pParent;
    }
    return pNext;
}