104. Maximum Depth of Binary Tree
此题是一道简单题,目的是为了开始厘清 DFS 和 BFS 算法的思路。
解法一 DFS
思路
首先想到如果给的数组是 null 则返回深度为零。可以这么想:一个节点的深度,就是它的 left child 和 right child 中深度较大的那个加一。
代码
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
}
复杂度分析
- 时间复杂度
- 所有结点都会经过一次, O(N)
- 空间复杂度 O(1)
- 最好情况: N 个节点形成了完全二叉树,recursion 运行 O(logN) 次
- 最坏情况: N 个节点都只有左孩子,recursion 运行 O(N) 次
解法二 Iteration
思路
使用 Stack 的 DFS。
对于一个节点,如果存在左节点或右节点,那么入栈,深度加一。
下一次 iteration 时,把入栈的节点弹出,查找该节点是否还有子节点。
有的话入栈,深度加一。没有就不用操作了,只是将这个节点出栈。
iteration 的过程直到栈中没有任何节点为止。
代码
class solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> level = new LinkedList<>();
// Initialize the LinkedList
stack.push(root);
level.push(1);
// Set the template to store node and max depth
TreeNode temp;
int curr_level, maxDepth = 0;
while (!stack.isEmpty()) {
temp = stack.pop(); // get the latest node in the stack
curr_level = level.pop(); // get the corresponding depth of the node
maxDepth = Math.max(maxDepth, curr_level); // 始终保持 max 最大
if (temp.left != null) {
stack.push(temp.left);
level.push(curr_level+1);
}
if (temp.right != null) {
stack.push(temp.right);
level.push(curr_level+1);
}
}
return maxDepth;
}
}
Takeaway
- 在此过程中,发现 LinkedList 同时具备 queue 和 stack 的功能。但需要创建时注意,使用
LinkedList
开头,不能使用list
。因为 List 接口中没有 push, add, poll 等方法。- 对 Linkedlist 接口方法的总结:
- 从 List 继承而来的: add() - 直接在 LinkedList 末端加入元素; remove() - 移除顶部元素; add(1, element) - 在 index = 1 的地方加入元素; set(1, element) - 在 index = 1 的地方替换元素
- LinkedList 自带方法: push() - 推入栈顶; pop(), poll()- 从栈顶出栈; pollLast(), pollFirst(), removeLast(); removeFirst() 顾名思义。
- 对 Linkedlist 接口方法的总结:
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: