LeetCode/104.Maximum_Depth_of_Binary_Tree.cpp at master · yuandong1222/LeetCode · GitHub

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <queue>
#include <iostream>

using namespace std;

//Definition for binary tree
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //return _maxDepth_Recursion(root);
        return _maxDepth_Iteration(root);
    }
    int _maxDepth_Recursion(TreeNode* root) {
        return _maxDepth_Recursion(root, 0);
    }
    int _maxDepth_Recursion(TreeNode* root, int current_depth) {
        if (root == NULL) {
            return 0;
        }

        int left_depth = _maxDepth_Recursion(root->left, current_depth);
        int right_depth = _maxDepth_Recursion(root->right, current_depth);

        int max_depth = left_depth > right_depth ? left_depth : right_depth;

        return max_depth + 1;
    }

    int _maxDepth_Iteration(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }

        int max_depth = 1;
        queue<pair<TreeNode*, int> > queue;
        queue.push(pair<TreeNode*, int>(root, 1));

        while (!queue.empty()) {
            pair<TreeNode*, int> node = queue.front();
            queue.pop();

            if (node.second > max_depth) {
                max_depth = node.second;
            }

            if(node.first->left != NULL) {
                queue.push(pair<TreeNode*, int>(node.first->left, node.second + 1));
            }
            if(node.first->right != NULL) {
                queue.push(pair<TreeNode*, int>(node.first->right, node.second + 1));
            }
        }

        return max_depth;
    }
};


class Solution_Test {
public:
    void test_case_1() {
        Solution solution;

        TreeNode n1(1);

        TreeNode n2(2);
        TreeNode n3(2);
        n1.left = &n2;
        n1.right = &n3;

        TreeNode n4(3);
        TreeNode n5(4);
        n2.left = &n4;
        n2.right = &n5;

        TreeNode n6(3);
        TreeNode n7(4);
        n3.left = &n7;
        n3.right = &n6;

        cout << solution.maxDepth(&n1) << endl;
    };
    void test_case_2() {
        Solution solution;

        TreeNode n1(1);

        TreeNode n2(2);
        TreeNode n3(2);
        n1.left = &n2;
        n1.right = &n3;

        TreeNode n4(3);
        n2.right = &n4;

        TreeNode n6(3);
        n3.right = &n6;

        cout << solution.maxDepth(&n1) << endl;
    };
    void test_case_3() {
        Solution solution;

        TreeNode n1(1);
        TreeNode n2(-42);
        TreeNode n3(-42);
        TreeNode n4(76);
        TreeNode n5(76);
        TreeNode n6(13);
        TreeNode n7(13);

        n1.left = &n2;
        n1.right = &n3;
        n2.right = &n4;
        n3.left = &n5;
        n4.right = &n6;
        n5.right = &n7;

        cout << solution.maxDepth(&n1) << endl;
    };
    void test_case_4() {
        Solution solution;

        TreeNode n1(1);
        TreeNode n2(2);

        n1.left = &n2;

        cout << solution.maxDepth(&n1) << endl;
    };
};
int main(int argc, char* argv[]) {
    Solution_Test solution_test;
    solution_test.test_case_1();
    solution_test.test_case_2();
    solution_test.test_case_3();
    solution_test.test_case_4();

    return 0;
};