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() 顾名思义。

本作品采用《CC 协议》，转载必须注明作者和本文链接