leetcode 104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree:题目链接

递归-DFS

AC:

class Solution {
    // DFS遍历了所有结点 时间复杂度O(N) 空间复杂度O(N) 
    // 递归宏观语义 返回二叉树的最大深度  
    public int maxDepth(TreeNode root) {
      if (root == null) {  // 递归终止条件
          return 0;
      }
      int leftMaxDepth = maxDepth(root.left);   // 递归求解左子树最大深度
      int rightMaxDepth = maxDepth(root.right); // 递归求解右子树最大深度
      return leftMaxDepth > rightMaxDepth ? leftMaxDepth+1 : rightMaxDepth + 1; // 返回左子树和右子树深度最大的 再加上 根节点
    }
}

BFS

第一种写法：在层次遍历的基础上，入队的时刻不止将当前结点入队，并且把当前结点的层数入队，用一个类(结构体)记录当前结点和其层数

class Solution {
    
    class Node{        
        TreeNode node; // 当前结点
        int level;     // 当前结点对应层数
        
        public Node(TreeNode node, int level){
            this.node = node;
            this.level = level;
        }
    }
    
    // 时间复杂度O(N)  空间复杂度O(M) M：队列大小
    public int maxDepth(TreeNode root) {
        if (root == null) {   // 如果树空
            return 0;
        }
        int res = 0;  // 存放结果 初始为0
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(root,1)); // 根节点入队
        while (!queue.isEmpty()) {     // 队列不空
            Node front = queue.poll(); // 队首结点出队
            if (front.level > res) {   // 如果队首结点的层次比res大 更新res
                res = front.level;
            }
            if (front.node.left != null) { // 队首元素左孩子不空 左孩子及其level入队
                queue.offer(new Node(front.node.left, front.level + 1));
            }
            if (front.node.right != null) { // 队首元素右孩子不空 右孩子及其level入队
                queue.offer(new Node(front.node.right, front.level + 1));
            }
        }
        return res;
    }
}

第二种写法：

class Solution {
    // 时间复杂度O(N)  空间复杂度O(M) M：队列大小
    public int maxDepth(TreeNode root) {
        if (root == null) {   // 如果树空
            return 0;
        }
        int res = 0;  // 存放结果 初始为0
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 根节点入队
        while (!queue.isEmpty()) {     // 队列不空
            res++;  // 层数+1
            // 取出当前层的结点 并将其孩子入队
            for (int size = queue.size(); size > 0; --size) {
                TreeNode front = queue.poll();
                if (front.left != null) {
                    queue.offer(front.left);
                }
                if (front.right != null) {
                    queue.offer(front.right);
                }
            }
        }
        return res;
    }
}