JZ38-二叉树的深度

一、递归实现
时间复杂度:O(n)
空间复杂度:O(n),当退化到链表的形式时

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

二、队列实现
(顶级接口)Collection-->Queue-->Deque-->LinkedList(实现类)
时间复杂度:O(n)
空间复杂度:O(n)

import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        //队列中 同层的结点会放在一起
        deque.push(root);
        //深度计数
        int count = 0;
        while (!deque.isEmpty()) {
            //记录下每层结点的个数
            int size =deque.size();
            while (size-- > 0) {
                //将当前层上所有的结点依次弹出队列
                TreeNode cur = deque.pop();
                if (cur.left != null) {
                    deque.addLast(cur.left);
                }
                if (cur.right != null) {
                    deque.addLast(cur.right);
                }
            }
            //一层全部的结点都出栈深度才加一
            count++;
        }
        return count;
    }
}