1.深度优先遍历（递归）ps:不好理解，所以我一般不喜欢用递归
思路
典型算法，用递归求出高度，每次都是深度优先。
具体算法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
else{
int lefth=maxDepth(root.left);
int righth=maxDepth(root.right);
return Math.max(lefth,righth)+1;
}
}
}2.深度优先遍历（栈）
思路
（1）设置两个栈，分别记录节点与对应节点的高度，因此要求同时进push与出pop
（2）采用前序遍历的方法，先将节点的右节点入栈，然后是左节点入栈，每次进栈高度均加一。然后每次循环都判断当前节点的高度是不是最高的。
具体代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int ans=0;
Deque<TreeNode> dq = new LinkedList<>();
Deque<Integer> nh = new LinkedList<>();
dq.push(root);
nh.push(1);
while(!dq.isEmpty()){
TreeNode currn = dq.pop();
int currh=nh.pop();
ans=Math.max(ans,currh);
if(currn.right!=null){
dq.push(currn.right);
nh.push(currh+1);
}
if(currn.left!=null){
dq.push(currn.left);
nh.push(currh+1);
}
}
return ans;
}
}3.广度优先遍历（队列1）
思路
和栈的思路一模一样，没有区别
具体代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int ans=0;
Deque<TreeNode> dq = new LinkedList<>();
Deque<Integer> h = new LinkedList<>();
dq.offer(root);
h.offer(1);
while(!dq.isEmpty()){
TreeNode n = dq.poll();
int curr = h.poll();
ans = Math.max(ans,curr);
if(n.left!=null){
dq.offer(n.left);
h.offer(curr+1);
}
if(n.right!=null){
dq.offer(n.right);
h.offer(curr+1);
}
}
return ans;
}
}4.广度优先遍历（队列2）
思路
计算二叉树的层数。
（1）每次循环将本层的节点全部抛出（dq.size()），将下一层的节点全部加入。
（2）没删除一层意味着ans+1.能删除多少层相当于层数有多少。
具体代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int ans=0;
Deque<TreeNode> dq = new LinkedList<>();
dq.offer(root);
while(!dq.isEmpty()){
int size = dq.size();
while(size>0){
TreeNode n = dq.poll();
if(n.left!=null){
dq.offer(n.left);
}
if(n.right!=null){
dq.offer(n.right);
}
size--;
}
ans++;
}
return ans;
}
}