leetcode104：二叉树的最大深度

题目链接

leetcode

题目描述

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

C++ 代码

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <vector>
#include <stack>
#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) {}
};

const int NULL_NODE = -101;

// 辅助函数：创建二叉树
TreeNode* createTree(const std::vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    std::queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    std::queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        std::cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    std::cout << std::endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    深度优先搜索，递归实现

    1.确定递归函数的参数和返回值
        参数是传⼊树的根结点，返回值是这棵树的深度。
    2.确定终⽌条件
        若树的根结点为空，就返回 0，表示高度为 0。
    3.确定单层递归的逻辑
        先求左⼦树的深度，再求右⼦树的深度，最后取左右深度最⼤值+1。
        +1 原因：算上当前中间结点，就是当前结点为根结点的树的深度。
    
    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，每个结点在递归中只被遍历一次。
    空间复杂度：O(n)
        主要取决于栈的大小，栈中存储了所有未被访问过的结点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到 O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是 O(logN)。
*/
class Solution_0 {
public:
    // 定义：输入一个结点，返回以该结点为根的二叉树的最大深度
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // 根据左右子树的最大深度，求出原二叉树的最大深度
        return 1 + max(leftMax, rightMax);
    }
};

/*
    递归，精简写法（不推荐）
    精简之后的代码根本看不出是哪种遍历⽅式，也看不出递归三部曲的步骤。
    如果对⼆叉树的操作还不熟练，尽量不要直接写精简代码。
    
    时间复杂度：O(n)
    空间复杂度：O(height)
*/
class Solution_1 {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

/*
    深度优先搜索，迭代实现（使用栈来模拟递归过程）

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
    空间复杂度：O(n)
        主要取决于栈的大小，栈中存储了所有未被访问过的结点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是O(logN)。
*/
class Solution_2 {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int depth = 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, 1});
        while (!stk.empty()) {
            TreeNode* node = stk.top().first;
            int tDepth = stk.top().second;
            stk.pop();

            if (node != nullptr) {
                depth = max(depth, tDepth);
                stk.push({node->left, tDepth + 1});
                stk.push({node->right, tDepth + 1});
            }
        }

        return depth;
    }
};

/*
    广度优先搜索，迭代实现

    时间复杂度：O(n)
        其中 n 是二叉树的结点数。
    空间复杂度：O(n)
        主要取决于队列的大小，队列中存储了所有未被访问过的结点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是O(logN)。
*/
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        int depth = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            while (n --) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            depth ++;
        }

        return depth;
    }
};

/*
    二叉树的中序遍历，迭代实现
*/
class Solution_4 {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        stack<pair<TreeNode*, int>> stk;
        int depth = 0, res = 0;
        while (root || stk.size()) {
            // 遍历到最左边的结点
            while (root) {
                stk.push({root, ++ depth});
                // 移动到左子结点
                root = root->left;
            }

            // 处理当前结点
            root = stk.top().first;
            depth = stk.top().second;
            stk.pop();
            if (res < depth) res = depth;

            // 移动到右子结点
            root = root->right;
        }

        return res;
    }
};

int main() {
    // 示例输入
    Solution solution;
    std::vector<int> nums = {3, 9, 20, NULL_NODE, NULL_NODE, 15, 7};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    // 打印二叉树
    levelOrderTraversal(root);

    // 计算最大深度
    int result = solution.maxDepth(root);
    // 打印结果
    std::cout << "Max Depth: " << result << std::endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package main

import "fmt"

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    深度优先搜索，递归实现

    基本思路：
        从根节点开始，如果节点为空则返回 0。
        否则，分别递归计算左子树和右子树的深度，
        然后取两者中的最大值再加 1，作为当前节点为根的子树的最大深度。

    时间复杂度：O(n)
        其中 n 为二叉树节点的个数，每个节点在递归中只被遍历一次。
    空间复杂度：O(n)
        其中 n 为二叉树节点的个数。
        主要取决于栈的大小，栈中存储了所有未被访问过的节点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是O(logN)。
*/
// 递归方式计算二叉树最大深度
func maxDepth_0(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    if leftDepth > rightDepth {
        return leftDepth + 1
    }

    return rightDepth + 1
}

/*
    广度优先搜索，迭代实现

    基本思路：
        使用一个队列进行层序遍历。
        先将根节点入队，然后每次取出队列中固定数量的节点（即当前层的节点），
        并将它们的非空左右子节点入队。每处理完一层，深度就加 1。
        直到队列为空，此时得到的深度就是二叉树的最大深度。

    时间复杂度：O(n)
        其中 n 是二叉树的节点数。
    空间复杂度：O(n)
        其中 n 为二叉树节点的个数。
        主要取决于栈的大小，栈中存储了所有未被访问过的节点及其深度。
        在最坏的情况下（当二叉树退化成链表时），栈的大小可能会达到O(N)。
        在最好的情况下（当二叉树完全平衡时），栈的大小将是O(logN)。
*/
// 迭代方式计算二叉树最大深度
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    queue := []*TreeNode{}
    queue = append(queue, root)
    depth := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i ++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        depth ++
    }

    return depth
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected int
    }{
        {
            values:   []int{3,9,20,-1,-1,15,7},
            expected: 3,
        },
        {
            values:   []int{1,-1,2},
            expected: 2,
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
        result := maxDepth(root)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}
#leetcode
leetcode104：二叉树的最大深度
https://lcf163.github.io/2024/03/31/leetcode104：二叉树的最大深度/
作者
乘风的小站
发布于
2024年3月31日
许可协议