leetcode104.二叉树的最大深度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

void CreatBinaryTreeByLevelVec(const vector<int>& vec, TreeNode* &cur, int index)
{
    if (index < vec.size() && vec[index] != -1) {
        cur = new TreeNode(vec[index]);
        CreatBinaryTreeByLevelVec(vec, cur->left, 2*index+1);
        if (2*index+2 < vec.size()) {
            CreatBinaryTreeByLevelVec(vec, cur->right, 2*index+2);
        }
    }
}


void CreatBinaryTreeByPreVec(const vector<int>& vec, TreeNode* &cur, int index)
{
    if (index < vec.size() && vec[index] != -1)//不能越界
    {
        cur = new TreeNode(vec[index]);
        cout << "cur: " << cur->val << endl;
        CreatBinaryTreeByPreVec(vec, cur->left, ++index);
        CreatBinaryTreeByPreVec(vec, cur->right, ++index);
    }
}

int maxDepthByDFS(TreeNode* root) {
    //DFS
    if (root == nullptr) return 0;
    return (max(maxDepthByDFS(root->left), maxDepthByDFS(root->right)) + 1);
}

int maxDepthByBFS(TreeNode* root) {
    //按照层来循环，每一层循环的长度为此层元素的个数，每次pop出最左侧的元素；如果该元素有子节点，将子节点加入队列；遍历完一层，ans+1
    if (root == nullptr) return 0;
    queue<TreeNode*> Q;
    Q.push(root);
    int ans = 0;
    while(!Q.empty()) {
        int len = Q.size();
        for (int i = 0; i < len; ++i) {
            TreeNode *node = Q.front();
            Q.pop();

            if (node->left) {
                Q.push(node->left);
            }
            if (node->right) {
                Q.push(node->right);
            }
        }
        ans += 1;
    }

    return ans;
}

int main() {
    vector<int> vec = {3,9,20,-1,-1,15,7};
    TreeNode* root = nullptr;
    CreatBinaryTreeByLevelVec(vec, root, 0);
//    int res = maxDepthByDFS(root);
    int res = maxDepthByBFS(root);
    std::cout << res << std::endl;
    return 0;
}