一、 104. 二叉树的最大深度
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
思路一：使用后序遍历，依次求出节点的高度，根节点的最大高度就是二叉树的最大深度
/**
* 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 leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 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 {
int result = 0;
private void maxDepth(TreeNode root, int depth) {
result = depth > result ? depth : result;
if (root.left == null && root.right == null) return;
if (root.left != null) {
depth++;
maxDepth(root.left, depth);
depth--;
}
if (root.right != null) {
depth++;
maxDepth(root.right, depth);
depth--;
}
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
maxDepth(root, 1);
return result;
}
}
思路三、使用层序遍历,求有总共多少层
/**
* 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 depth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
while (size-- > 0) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
}
return depth;
}
}
二、559. N 叉树的最大深度
题目链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
思路一、使用后序遍历，求每个节点的最大高度
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) return 0;
int maxDepth = 0;
for (int i = 0; root.children != null && i < root.children.size(); i++) {
maxDepth = Math.max(maxDepth, maxDepth(root.children.get(i)));
}
return maxDepth + 1;
}
}
思路二：前序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
private int result = 0;
private void maxDepth(Node root, int depth) {
result = depth > result ? depth : result;
if (root.children == null || root.children.isEmpty()) return;
for (int i = 0; i < root.children.size(); i++) {
Node childNode = root.children.get(i);
if (childNode != null) {
depth++;
maxDepth(childNode, depth);
depth--;
}
}
}
public int maxDepth(Node root) {
if (root == null) return result;
maxDepth(root, 1);
return result;
}
}
思路三、层序遍历
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) return 0;
int depth = 0;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
while (size-- > 0) {
Node node = queue.poll();
for (int i = 0; node.children != null && i < node.children.size(); i++) {
queue.offer(node.children.get(i));
}
}
}
return depth;
}
}
三、 111. 二叉树的最小深度
题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
思路一：后序遍历
/**
* 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) {
if (root == null) return 0;
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left != null && root.right == null) {
return 1 + leftDepth;
}
if (root.left == null && root.right != null) {
return 1 + rightDepth;
}
return Math.min(leftDepth, rightDepth) + 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 {
int result = Integer.MAX_VALUE;
private void minDepth(TreeNode root, int depth) {
if (root.left == null && root.right == null) {
result = result > depth ? depth : result;
return;
}
if (root.left != null) {
minDepth(root.left, depth + 1);
}
if (root.right != null) {
minDepth(root.right, depth + 1);
}
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
minDepth(root, 1);
return result;
}
}
思路三：层序遍历
/**r
* 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) {
if (root == null) return 0;
int depth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
depth++;
while (size-- > 0) {
TreeNode treeNode = queue.poll();
if (treeNode.left == null && treeNode.right == null) return depth;
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
}
return depth;
}
}
四、 222. 完全二叉树的节点个数
题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/
思路一、当作一个普通的二叉树可使用后序、层序等
//后序迭代法
/**
* 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;
int leftCount = countNodes(root.left);
int rigthCount = countNodes(root.right);
return leftCount + rigthCount + 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 countNodes(TreeNode root) {
if (root == null) return 0;
int result = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
result++;
TreeNode treeNode = queue.poll();
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
}
return result;
}
}
思路二、使用后序遍历，并利用完全二叉树特性
/**
* 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;
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
int leftCount = 0;
int rightCount = 0;
while (leftNode != null) {
leftNode = leftNode.left;
leftCount++;
}
while (rightNode != null) {
rightNode = rightNode.right;
rightCount++;
}
if (leftCount == rightCount) {
return (2 << leftCount) - 1;
}
leftCount = countNodes(root.left);
rightCount = countNodes(root.right);
return leftCount + rightCount + 1;
}
}
网友评论