一、递归实现
时间复杂度: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; } }