跳转至

6. 解决问题的思路

面试题27: 二叉树的镜像

struct Node
{
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
};

void exchangeChild(Node* pNode);

void treeMirror(Node* pRoot)
{
    if (pRoot == nullptr)
        return;

    exchangeChild(pRoot);
}

void exchangeChild(Node* pNode)
{
    if (pNode == nullptr)
        return;

    Node* left = pNode->left;
    Node* right = pNode->right;

    pNode->left = right;
    pNode->right = left;
    exchangeChild(pNode->left);
    exchangeChild(pNode->right);
}

完整代码: 树的镜像

面试题28: 对称的二叉树

bool isSymmetric(Node* pRoot1, Node* pRoot2)

bool isSymmetric(Node* pRoot)
{
    return isSymmetric(pRoot->pLeft, pRoot->pRight);
}

bool isSymmetric(Node* pRoot1, Node* pRoot2)
{
    if (pRoot1 == nullptr || pRoot2 == nullptr)
        return false;

    if (pRoot1->value != pRoot2->value)
        return false;

    if (pRoot1 == nullptr && pRoot2 == nullptr)
        return true;

    return isSymmetric(pRoot1->pLeft, pRoot2->pRight)
        && isSymmetric(pRoot1->pRight, pRoot2->pLeft);
}

完整代码: 对称的二叉树

面试题29: 顺时针打印矩阵

面试题30: 包含min函数的栈

面试题31: 栈的压入,弹出序列

bool isPopOrder(vector<int>& pushVector, vector<int>& popVector)
{
    if (pushVector.size() <= 0 || popVector.size() <= 0)
        return false;

    stack<int> stackTemp;
    unsigned int pushVectorIndex = 0;
    unsigned int popVectorIndex = 0;

    stackTemp.push(pushVector[pushVectorIndex++]);

    while (popVectorIndex < popVector.size())
    {
        while (stackTemp.top() != popVector[popVectorIndex])
        {
            if (pushVectorIndex >= pushVector.size())
                break;
            stackTemp.push(pushVector[pushVectorIndex++]);
        }

        if (stackTemp.top() != popVector[popVectorIndex])
            break;

        stackTemp.pop();
        popVectorIndex++;
    }
    if (stackTemp.empty())
        return true;
    return false;
}

完整代码: 栈的压入,弹出序列

面试题32: 从上到下打印二叉树

struct Node
{
    int value;
    Node* pLeft = nullptr;
    Node* pRight = nullptr;
};


vector<int> printBTreeOfLayer(Node* pRoot)
{
    vector<int> vectorResult;
    if (pRoot == nullptr)
        return vectorResult;

    queue<Node*> queueNodes;
    queueNodes.push(pRoot);
    vectorResult.push_back(pRoot->value);

    Node* node = nullptr;
    while (queueNodes.size() > 0)
    {
        node = queueNodes.front();
        queueNodes.pop();
        if (node->pLeft != nullptr)
        {
            queueNodes.push(node->pLeft);
            vectorResult.push_back(node->pLeft->value);
        }

        if (node->pRight != nullptr)
        {
            queueNodes.push(node->pRight);
            vectorResult.push_back(node->pRight->value);
        }
    }
    return vectorResult;
}

参考代码: 从上到下打印二叉树

面试题33: 二叉搜索树的后序遍历序列

bool isSequenceOfBST(int sequence[], int length)
{
    if (sequence == nullptr || length <= 0)
        return false;

    int root = sequence[length - 1];
    int i = 0;

    for (; i < length - 1; ++i)
    {
        if (sequence[i] > root)
            break;
    }

    int j = i + 1;
    for (; j < length - 1; ++j)
    {
        if (sequence[j] < root)
            return false;
    }

    bool left = true;
    if (i > 0)
        return isSequenceOfBST(sequence, i);

    bool right = true;
    if (i < length - 1)
        return isSequenceOfBST(sequence + i, length - i - 1);

    return left && right;
}

面试题34: 二叉树中和为某一值的路径

struct Node
{
    int value;
    Node* pLeft = nullptr;
    Node* pRight = nullptr;
};

void findPath(Node* pNode, int expectSum, vector<int> vectorPath, int curSum);

void findPath(Node* pRoot, int expectSum)
{
    if (pRoot == nullptr)
        return;

        vector<int> vectorPath;
    int curSum = 0;
    findPath(pRoot, expectSum, vectorPath, curSum);
}

void findPath(Node* pNode, int expectSum, vector<int> vectorPath, int curSum)
{
    if (pNode == nullptr)
        return;

    vectorPath.push_back(pNode->value);
    curSum += pNode->value;
    // 如果路径上的节点的和等于 expectSum
    // 则打印出路径
    bool isLeaf = pNode->pLeft == nullptr && pNode->pRight == nullptr;
    if (curSum == expectSum && isLeaf)
    {
        vector<int>::iterator iter = vectorPath.begin();
        for (; iter != vectorPath.end(); iter++)
        {
            cout << *iter << ' ';
        }
        cout << endl;
    }

    // 继续查找左右子节点
    findPath(pNode->pLeft, expectSum, vectorPath, curSum);
    findPath(pNode->pRight, expectSum, vectorPath, curSum);

    // 在返回父节点之前,在路径上删除当前节点
    vectorPath.pop_back();
}

面试题35: 复杂链表的复制

参考代码: 复杂链表的复制