Depth & Diameter
"Top-down" Solution
"Top-down" means that in each recursive call, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively. So the "top-down" solution can be considered as a kind of preorder traversal. To be specific, the recursive function top_down(root, params) works like this:
1. return specific value for null node
2. update the answer if needed // answer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
private void maximum_depth(TreeNode root, int depth) {
if (root == null) return;
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}"Bottom-up" Solution
"Bottom-up" is another recursive solution. In each recursive call, we will firstly call the function recursively for all the children nodes and then come up with the answer according to the returned values and the value of the current node itself. This process can be regarded as a kind of postorder traversal. Typically, a "bottom-up" recursive function bottom_up(root) will be something like this:
1. return specific value for null node
2. left_ans = bottom_up(root.left) // call function recursively for left child
3. right_ans = bottom_up(root.right) // call function recursively for right child
4. return answers // answer <-- left_ans, right_ans, root.val
public int maximum_depth(TreeNode root) {
if (root == null) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);
return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}When you meet a tree problem, ask yourself two questions: Can you determine some parameters to help the node know its answer? Can you use these parameters and the value of the node itself to determine what should be the parameters passed to its children? If the answers are both yes, try to solve this problem using a "top-down" recursive solution.
Or, you can think of the problem in this way: for a node in a tree, if you know the answer of its children, can you calculate the answer of that node? If the answer is yes, solving the problem recursively using a bottom up approach might be a good idea.
bottom up
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}class Solution {
public int maxDepth(Node root) {
if (root == null) return 0;
int res = 0;
//recursive
// for (Node node : root.children) {
// res = Math.max(res, maxDepth(node));
// }
// return res + 1;
//iterative
Queue<Node> q = new LinkedList<>();
q.add(root);
int count = 0;
while(!q.isEmpty()) {
res++; // 每经过一层，需要+1
count = q.size(); // 这里需要把size存下来，因为后面会往q里加的node
for (int i = 0; i < count; i++) {
Node node = q.poll();
for (Node n : node.children) {
q.add(n);
}
}
}
return res;
}
}Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its minimum depth = 2.
My Solutions:
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
// if root has both children, return the min one
if (root.left != null && root.right != null) {
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
// if root only has left/right child, return the max one
else {
return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
}
}
}199。Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]My Solutions:
/**
* 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 List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res, 0);
return res;
}
private void helper(TreeNode root, List<Integer> res, int level) {
if (root == null) return;
if (level == res.size()) res.add(root.val); // this line will add one element to result for one level only
helper(root.right, res, level + 1); // go to right side first
helper(root.left, res, level + 1);
}
}Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
1
/ \
2 3
/ \
4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them. My solutions：
这道题的意思是求任意两个node之间的最长路径，因此需要一个全局变量来记录这个最大值。
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
di(root);
return ans;
}
public int di(TreeNode root) {
if (root == null) return 0;
int left = di(root.left);
int right = di(root.right);
ans = Math.max(ans, left + right); //diameter不需要加1.更新结果的最大值
//只可以在left和right path中选择一条路，所以这里需要+1
return Math.max(left, right) + 1;
}
}Last updated