二叉树的最大深度

发表于

递归

这是一个leetcode的题目。给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
/** 树的定义 */
class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	ThreeNode(int x){
		this.val = x;
	}
}

看到树，一般最先想到的是使用递归来解题。

1
2
3
4
5
6
public int maxDepth(TreeNode root){
  if(root==null){
    return 0;
  }
  return Math.max(maxDepth(root.left,maxDepth(root.right)+1;
}

迭代

利用栈先进后出的原理，来对树的深度进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxDepth(TreeNode root){
			LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
       stack.add(new Pair<>(root, 1));
       int dept = 0;
       while (!stack.isEmpty()) {
           Pair<TreeNode, Integer> node = stack.poll();
           root = node.getKey();
           int curr = node.getValue();
           if (root != null) {
               dept = Math.max(dept, curr);
               stack.add(new Pair<>(root.left, curr + 1));
               stack.add(new Pair<>(root.right, curr + 1));
           }
       }
       return dept;
}