Question

这2道数据结构题怎么解答啊？

Answer 1

1、归并排序

归并排序的思想就是递归地将数组的前半部分和后半部分数据各自归并排序，得到排序后的两部分数据，在用合并算法进行合并。

对于本题而言，首先对前四个数归并排序，分成两部分：

38,49；(1)

65,97；(2)

合并(1)(2)得到：38,49,65,97；(3)

然后对后四个数归并排序，分成两部分：

13,76；(4)

27,49；(5)

合并(4)(5)得到：13,27,49,76；(6)

最后合并(3)(6)得到：13,27,38,49,49,76,97；即为最终结果！

2、二叉树

#include <iostream>
#include <stack>
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void maxDepthAndNodesNum(TreeNode *root)
{
    if (root == NULL)
    {
        std::cout << "max depth: " << 0 << std::endl;
        std::cout << "nodes num: " << 0 << std::endl;
    }
    int max_depth = 0, nodes_num = 0;
    std::deque<TreeNode *> nodes;
    nodes.push_back(root);
    while (!nodes.empty())
    {
        max_depth++;
        std::size_t count = nodes.size();
        nodes_num = nodes_num + count;
        for (std::size_t i = 0; i != count; ++i)
        {
            root = nodes.front();
            if (root->left != NULL)
            {
                nodes.push_back(root->left);
            }
            if (root->right != NULL)
            {
                nodes.push_back(root->right);
            }
            nodes.pop_front();
        }
    }
    std::cout << "max depth: " << max_depth << std::endl;
    std::cout << "nodes num: " << nodes_num << std::endl;
}
int main(int argc, char const *argv[])
{
    TreeNode node1(3), node2(4), node3(6), node4(8), node5(9);
    node1.left = &node2;
    node1.right = &node3;
    node2.left = &node4;
    node2.right = &node5;
    maxDepthAndNodesNum(&node1);
    getchar();
    return 0;
}