04.二叉树的最大深度
/**
* 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) {
int a = dfs(root);
return a;
}
int dfs(TreeNode root){
if (root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
return Math.max(left,right) + 1;
}
}
111.二叉树的最小深度
/**
* 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 minDepth(TreeNode root) {
int a = dfs(root);
return a;
}
public int dfs(TreeNode root){
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
if(root.left != null && root.right == null){
return left + 1;
}
if(root.left == null && root.right != null){
return right + 1;
}
int result = Math.min(left,right)+1;
return result;
}
}
222.完全二叉树的节点个数
采用层次遍历:
时间复杂度O(n)
空间复杂度O(n)
/**
* 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 countNodes(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> queue= new LinkedList<>();
queue.offer(root);
int nums = 0;
while(!queue.isEmpty()){
int len = queue.size();
nums += len;
while(len > 0){
TreeNode temp = queue.poll();
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
len--;
}
}
return nums;
}
}
如果采用上一种方法,没有使用完全二叉树的条件不太合理。
普通递归法:
/**
* 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 countNodes(TreeNode root) {
int result = f(root);
return result;
}
int f(TreeNode root){
if(root == null) return 0;
return f(root.left) + f(root.right) + 1;
}
}
利用完全二叉树的规律:
时间复杂度(lgn * lgn)
空间复杂度(lgn)
/**
* 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 countNodes(TreeNode root) {
int result = f(root);
return result;
}
int f(TreeNode root){
if(root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int depthleft = 0,depthright = 0;
while(left != null){
left = left.left;
depthleft++;
}
while(right != null){
right = right.right;
depthright++;
}
if(depthleft == depthright){
return (2 << depthleft) - 1;
}
return f(root.left) + f(root.right) + 1;
}
}