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