二叉树的最大深度

问题陈述

给定一棵二叉树，求其深度。

问题详解

1、递归

class Solution{
    public int maxDeep(TreeNode root){
        if(root==null) return 0;
        int left=maxDeep(root.left);
        int right=maxDeep(root.right);
        return Math.max(left,right)+1;
    }
}

基于BFS的思想

public int maxDeep(TreeNode root){
    if(root==null) return 0;
    LinkedList<TreeNode> list=new LinkedList<>();
    list.add(root);
    int maxDepth=0;
    while(!list.isEmpty()){
        maxDepth++;
        int levelsize=list.size();
        for(int i=0;i<levelsize;i++){
            TreeNode node=list.poll();
            if(node.left!=null) list.add(node.left);
            if(node.right!=null) list.add(node.right);
        }
    }
    return maxDepth;
}

基于DFS的思想

/**
 * DFS迭代实现二叉树最大深度
 * 时间复杂度O(n)
 * 空间复杂度:线性表最差O(n)、二叉树完全平衡最好O(logn)
 *
 * @param root 根节点
 * @return 最大深度
 */
private static int maxDepth2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    stack.push(new Pair<>(root, 1));
    int maxDepth = 0;
    //DFS实现前序遍历，每个节点记录其所在深度
    while (!stack.isEmpty()) {
        Pair<TreeNode, Integer> pair = stack.pop();
        TreeNode node = pair.first;
        //DFS过程不断比较更新最大深度
        maxDepth = Math.max(maxDepth, pair.second);
        //记录当前节点所在深度
        int curDepth = pair.second;
        //当前节点的子节点入栈，同时深度+1
        if (node.right != null) {
            stack.push(new Pair<>(node.right, curDepth + 1));
        }
        if (node.left != null) {
            stack.push(new Pair<>(node.left, curDepth + 1));
        }
    }
    return maxDepth;
}