• 树是一种在实际编程中经常遇到的数据结构。它的逻辑很简单：除了根结点之外每个结点只有一个父结点，根结点没有父结点；除了叶结点之外所有结点都有一个或多个子结点，叶结点没有子结点。父结点和子结点之间用指针链接。
    • 树的操作会涉及大量的指针，因此与树有关的面试题都不太容易。
    • 二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。

    通常树有如下几种遍历方式：
    ● 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
    ● 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
    ● 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
    image.png

    • 前序遍历：10、6、4、8、14、12、16
    • 中序遍历：4、6、8、10、12、14、16
    • 后序遍历：4、8、6、12、16、14、10

    3种遍历都有递归和循环两种不同的实现方法，每一种遍历的递归实现都比循环实现要简捷很多

    ● 宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中，以从左到右的顺序依次访问。我们可以对包括二叉树在内的所有树进行宽度优先遍历。

    二叉树有很多特例，二叉搜索树就是其中之一；在二叉搜索树中，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。
    二叉树的另外两个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根结点的值最大，在最小堆中根结点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。
    红黑树是把树中的结点定义为红、黑两种颜色，并通过规则确保从根结点到叶结点的最长路径的长度不超过最短路径的两倍。

    输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出图2.6所示的二叉树并输出它的头结点。二叉树结点的定义如下：

    1. struct BinaryTreeNode
    2. {
    3.     int             m_nValue;
    4.     BinaryTreeNode*    m_pLeft;
    5.     BinaryTreeNode* m_pRight;
    6. };

    在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。
    但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

    在中序遍历序列中，有 3 个数字是左子树结点的值，因此左子树总共有3 个左子结点。同样，在前序遍历的序列中，根结点后面的3 个数字就是 3 个左子树结点的值，再后面的所有数字都是右子树结点的值

    image.png
    递归

    1. BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
    2. {
    3.     if((preorder == NULL) || (inorder == NULL) || (length <= 0)){
    4.         return NULL;
    5.     }
    6.     return ConstructCore(preorder, preorder+length-1, inorder, inorder+length-1);
    7. }
    9. /* startPreorder    : 起始遍历起始位置
    10.  * endPreorder        : 前序遍历末尾位置
    11.  * satartInorder    : 中序遍历起始位置
    12.  * endInorder        : 中序遍历末尾位置
    13.  */
    14. BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
    15. {
    16.     /* 前序遍历序列的第一个数字是根节点的值 */
    17.     int rootValue = startPreorder[0];
    18.     BinaryTreeNode* root = new BinaryTreeNode();    //创建节点
    19.     root->m_nValue = rootValue;
    20.     root->m_pLeft = root->m_pRight = NULL;
    22.     /* 前序遍历只有一个节点了 */
    23.     if(startPreorder == endPreorder)
    24.     {
    25.         /* 中序遍历也只有一个节点，并且两者相等 */
    26.         if((startInorder == endInorder) && (*startPreorder == *startInorder))
    27.             return root;
    28.         else
    29.             throw std::exception("Invalid input.");    //抛出异常
    30.     }
    32.     // 在中序遍历中找到根节点的值
    33.     int* rootInorder = startInorder;
    34.     while((rootInorder <= endInorder) && (*rootInorder != rootValue))
    35.         ++rootInorder;
    37.     /* 中序遍历根节点等于中序遍历末尾，并且中序遍历根节点值不等于前序列的根节点值 */
    38.     if((rootInorder == endInorder) && (*rootInorder != rootValue))
    39.         throuw std::exception("invalid input.");
    41.     int leftLength = rootInorder - startInorder;        //得到左子节点数
    42.     int* leftPreorderEnd = startPreorder + leftLength;    //前序遍历中左子节点的最后一个
    43.     if(leftLength > 0)
    44.     {
    45.         //构建左子树
    46.         root->m_pLeft = ConstructCore(startPreorder+1, leftPreorderEnd, startInorder, rootInorder-1);        //递归
    47.     }
    48.     if(leftLength < endPreorder - startPreorder)
    49.     {
    50.         //构建右子树
    51.         root->m_pRight = ConstructCore(leftPreorderEnd+1, endPreorder, rootInorder+1, endInorder);
    52.     }
    54.     return root;
    55. }

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