面试office，Careercup - Microsoft面试题 - 5672369481842688

2023-09-20 阅读 13 评论 0

摘要：2014-05-12 06:27 题目链接原题： Find the max height of a binary tree. 题目：计算二叉树的最大高度。解法：最大高度？高度不就是最深的叶子节点到根节点的路径长度吗？我就当是高度吧，递归解决。面试office，代码： 1 //

2014-05-12 06:27

题目链接

原题：

Find the max height of a binary tree.

题目：计算二叉树的最大高度。

解法：最大高度？高度不就是最深的叶子节点到根节点的路径长度吗？我就当是高度吧，递归解决。

面试office，代码：

 1 // http://www.careercup.com/question?id=5672369481842688
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <sstream>
 5 #include <string>
 6 using namespace std;
 7 
 8 struct TreeNode {
 9     int val;
10     TreeNode *left;
11     TreeNode *right;
12     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};
13 };
14 
15 int height(TreeNode *root)
16 {
17     return root ? 1 + max(height(root->left), height(root->right)) : 0;
18 }
19 
20 void constructBinaryTree(TreeNode *&root)
21 {
22     static int val;
23     static string str;
24     static stringstream sio;
25     
26     if (cin >> str && str != "#") {
27         sio << str;
28         sio >> val;
29         root = new TreeNode(val);
30         constructBinaryTree(root->left);
31         constructBinaryTree(root->right);
32     } else {
33         root = nullptr;
34     }
35 }
36 
37 void deleteTree(TreeNode *&root)
38 {
39     if (root == nullptr) {
40         return;
41     } else {
42         deleteTree(root->left);
43         deleteTree(root->right);
44         delete root;
45         root = nullptr;
46     }
47 }
48 
49 int main()
50 {
51     TreeNode *root;
52     
53     while (true) {
54         constructBinaryTree(root);
55         if (root == nullptr) {
56             break;
57         }
58         cout << height(root) << endl;
59         deleteTree(root);
60     }
61     
62     return 0;
63 }