二叉树的最大深度

题目描述

思路一：递归

首先要清楚树的高度在数值上等于树的深度。每到一个结点求当前结点的左子树和右子树高度，如果当前结点为空，则意味着以当前节点为根结点的树不存在高度为0，返回0。如果当前结点不为空，则分别进入其左、右子树，计算左、右子树的高度，并返回最大高度加1。加一是因为返回的高度是左、右子树的高度，加的1代表子树根结点的高度。 //递归实现 class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; //计算左子树高度 int m=maxDepth(root.left); //计算右子树高度 int n=maxDepth(root.right); if(m>n) return m+1; else return n+1; } }

思路二：DFS

深度优先一般采用栈来实现，从根结点开始沿着左分支或右分支不断深入。每访问一个结点就把当前结点和其所在深度压入栈中。当栈不空时，弹出栈顶元素，比较当前最大深度和该结点最大深度，取最大值。然后将当前的左孩子和右孩子分别压入栈中。

//DFS实现 class Solution { //栈帧 public static class Pair{ TreeNode node; int depth; public Pair(TreeNode node,int depth){ this.node = node; this.depth = depth; } } public int maxDepth(TreeNode root) { int max_depth=0; if(root==null) return max_depth; Stack<Pair> stack=new Stack<>(); //压入根结点 stack.push(new Pair(root,1)); while(!stack.isEmpty()){ Pair pair=stack.pop(); TreeNode node=pair.node; int depth=pair.depth; max_depth=Math.max(max_depth,depth); //以下两个分支可以交换次序 if(node.right!=null){ stack.push(new Pair(node.right,depth+1)); } if(node.left!=null){ stack.push(new Pair(node.left,depth+1)); } } return max_depth; } }

思路三：BFS

每遍历一层，就将深度加1。通常使用队列实现。

class Solution { public int maxDepth(TreeNode root) { int max_depth=0; if(root==null) return max_depth; // bfs Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int size=queue.size(); max_depth++; for(int i=0;i<size;i++){ //出队 TreeNode node=queue.poll(); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } } return max_depth; } }