# 面试题 7:重建二叉树

# 题目

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

struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
}

binary_tree_rebuild

# 思路

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

根据前序遍历序列,我们能够找到当前树的根节点;然后在中序遍历序列中,根据根节点的位置,判断左子树和右子树的节点数量。由此可以在前序遍历的序列中确定左子树和右子树的分界点。之后,对于左子树和右子树重复上述过程,即可完成重建。

# 代码

#include <iostream>
#include <vector>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
BinaryTreeNode *build_core(vector<int>::iterator pre_begin, vector<int>::iterator pre_end,
                           vector<int>::iterator in_begin, vector<int>::iterator in_end) {
     if (pre_begin == pre_end || in_begin == in_end) {
        return nullptr;
    }
    int root_val = *pre_begin;
    BinaryTreeNode *root = new BinaryTreeNode();
    root->m_value = root_val;
    root->m_left = root->m_right = nullptr;
    vector<int>::iterator root_inorder_it = in_begin;
    while (root_inorder_it < in_end && *root_inorder_it != root_val) {
        ++root_inorder_it;
    }
    if (root_inorder_it == in_end) {
        return nullptr;
    }
    int left_len = root_inorder_it - in_begin;
    int right_len = in_end - root_inorder_it - 1;
    if (left_len > 0) {
        root->m_left = build_core(pre_begin + 1, pre_begin + left_len + 1, in_begin, root_inorder_it);
    }
    if (right_len > 0) {
        root->m_right = build_core(pre_begin + left_len + 1, pre_end, root_inorder_it + 1, in_end);
    }
    return root;
}
BinaryTreeNode *build(vector<int> preorder, vector<int> inorder) {
    if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) {
        return nullptr;
    }
    return build_core(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}#include <iostream>
#include <vector>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
};
BinaryTreeNode *build_core(vector<int>::iterator pre_begin, int pre_len,
                           vector<int>::iterator in_begin, int in_len) {
    int root_val = *pre_begin;
    BinaryTreeNode *root = new BinaryTreeNode();
    root->m_value = root_val;
    root->m_left = root->m_right = nullptr;
    if (pre_len == 1) {
        if (in_len == 1 && *pre_begin == *in_begin) {
            return root;
        } else {
            throw exception("Invalid input.");
        }
    } else if (pre_len != in_len) {
        throw exception("Invalid input.");
    }
    vector<int>::iterator root_inorder_it = in_begin;
    while (root_inorder_it < in_begin + in_len && *root_inorder_it != root_val) {
        ++root_inorder_it;
    }
    if (root_inorder_it == in_begin + in_len) {
        throw exception("Invalid input.");
    }
    int left_len = root_inorder_it - in_begin;
    int right_len = in_len - left_len - 1;
    if (left_len > 0) {
        root->m_left = build_core(pre_begin + 1, left_len, in_begin, left_len);
    }
    if (right_len > 0) {
        root->m_right = build_core(pre_begin + left_len + 1, right_len, in_begin, right_len);
    }
    return root;
}
BinaryTreeNode *build(vector<int> preorder, vector<int> inorder) {
    if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) {
        return nullptr;
    }
    return build_core(preorder.begin(), preorder.size(), inorder.begin(), inorder.size());
}

# 面试题 8:二叉树的下一个节点

# 题目

给定一棵二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?树中的节点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针。

# 思路

如果一个节点有右子树,那么它的下一个节点就是它的右子树中的最左节点。

如果一个节点没有右子树,并且是其父节点的左子节点,那么它的下一个节点就是它的父节点。

如果一个节点没有右子树,并且是其父节点的右子节点,那么需要沿着父节点遍历,直到找到一个节点,这个节点是它的父节点的左子节点。如果这样的节点不存在,说明最开始的节点是树中的最右节点,没有下一个节点。

上述的下一个节点,即一个节点的后继 (successor);对应地,前一个节点称为前驱 (predecessor)。

针对不同的遍历方式,如前序遍历和后序遍历,前驱和后继表示的节点也不相同,这里暂时不详细讨论。

# 代码

#include <iostream>
#include <vector>
using namespace std;
struct BinaryTreeNode {
    int m_value;
    BinaryTreeNode *m_left;
    BinaryTreeNode *m_right;
    BinaryTreeNode *m_parent;
};
BinaryTreeNode *inorder_successor(BinaryTreeNode *node) {
    if (node == nullptr) {
        return nullptr;
    }
    BinaryTreeNode *next = nullptr;
    // 如果节点有右子树,寻找右子树的最左节点
    if (node->m_right != nullptr) {
        BinaryTreeNode *right = node->m_right;
        while (right->m_left != nullptr) {
            right = right->m_left;
        }
        next = right;
    } else if (node->m_parent != nullptr) {
        BinaryTreeNode *cur = node;
        BinaryTreeNode *parent = node->m_parent;
        while (parent != nullptr && cur == parent->m_right) {
            cur = parent;
            parent = parent->m_parent;
        }
        next = parent;
    }
    return next;
}

# 面试题 9:用两个栈实现队列

# 题目

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 append_taildelete_head ,分别完成在队列尾部插入节点和在队列头部删除节点的功能。

template<typename T> class Queue {
public:
    Queue();
    ~Queue();
    void append_tail(const T& node);
    T delete_head();
private:
    stack<T> stack1;
    stack<T> stack2;
}

# 思路

对于两个栈 stack1stack2stack1 用于插入元素,而 stack2 则用于删除元素。

当有元素插入时,直接插入到 stack1 中;

当删除元素时,如果 stack2 为空,则将 stack1 中的元素依次弹出插入到 stack2 中,这时 stack2 中的元素出栈的顺序和 stack1 中的元素入栈的顺序一致,即模拟了队列的先进先出的性质;而如果 stack2 不为空,此时栈顶的元素对应队列的队首元素,可以直接删除栈顶的元素。

# 代码

#include <iostream>
#include <stack>
using namespace std;
template<typename T> class Queue {
public:
    Queue();
    ~Queue();
    void append_tail(const T& element);
    T delete_head();
private:
    stack<T> stack1;
    stack<T> stack2;
};
template<typename T>
void Queue<T>::append_tail(const T &element) {
    stack1.push(element);
}
template<typename T>
T Queue<T>::delete_head() {
    if (stack2.size() <= 0) {
        while (stack1.size() > 0) {
            T &data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }
    if (stack2.size() == 0) {
        throw "Queue is empty";
    }
    T head = stack2.top();
    stack2.pop();
    return head;
}