day19 leetcode-hot100-37（二叉树2）

104. 二叉树的最大深度 - 力扣（LeetCode）

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;}
}