Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
难度：easy
Solution: Recursive
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private void maxDepthHelper(TreeNode root, int curDep, int[] maxDep) {
if(root == null) {
maxDep[0] = Math.max(curDep, maxDep[0]);
return;
}
maxDepthHelper(root.left, curDep + 1, maxDep);
maxDepthHelper(root.right, curDep + 1, maxDep);
}
public int maxDepth(TreeNode root) {
int[] maxDep = new int[1];
maxDepthHelper(root, 0, maxDep);
return maxDep[0];
}
}
另一个更加简洁的方法。
public class Solution {
public int maxDepth(TreeNode root) {
return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}
Solution: Iterative
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
TreeNode node = root;
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> depthStack = new Stack<Integer>();
int max = 0;
int depth = 1;
while (node != null || !nodeStack.isEmpty())
{
if (node != null)
{
nodeStack.push(node);
depthStack.push(depth);
node = node.left;
depth++;
}
else
{
node = nodeStack.pop();
depth = depthStack.pop();
if (depth > max) max = depth;
node = node.right;
depth++;
}
}
return max;
}
}
Minimum Depth of Binary Tree
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.
Solution: DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
} else if(root.left != null && root.right == null) {
return minDepth(root.left) + 1;
} else if(root.left == null && root.right != null) {
return minDepth(root.right) + 1;
} else {
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
}
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
难度：easy
Solution: DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private boolean isBalancedHelper(TreeNode root, int[] height) {
if(root == null) {
height[0] = 0;
return true;
}
int[] left = new int[1];
if(!isBalancedHelper(root.left, left)) {
return false;
}
int[] right = new int[1];
if(!isBalancedHelper(root.right, right)) {
return false;
}
height[0] = Math.max(left[0], right[0]) + 1;
return Math.abs(left[0] - right[0]) <= 1;
}
public boolean isBalanced(TreeNode root) {
return isBalancedHelper(root, new int[1]);
}
}
Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
难度：easy
Solution: DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null) {
return false;
}
if(root.left == null && root.right == null) {
return sum == root.val;
} else if(root.left == null && root.right != null) {
return hasPathSum(root.right, sum - root.val);
} else if(root.left != null && root.right == null) {
return hasPathSum(root.left, sum - root.val);
} else {
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
}
Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
难度：medium
Solution: DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private void pathSumHelper(TreeNode root, int sum, List<List<Integer>> res, List<Integer> tempRes) {
tempRes.add(root.val);
if(root.left == null && root.right == null) {
if(root.val == sum) {
res.add(new ArrayList<Integer>(tempRes));
}
} else if(root.left == null && root.right != null) {
pathSumHelper(root.right, sum - root.val, res, tempRes);
} else if(root.left != null && root.right == null) {
pathSumHelper(root.left, sum - root.val, res, tempRes);
} else {
pathSumHelper(root.left, sum - root.val, res, tempRes);
pathSumHelper(root.right, sum -root.val, res, tempRes);
}
tempRes.remove(tempRes.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
pathSumHelper(root, sum, res, new ArrayList<Integer>());
return res;
}
}
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
难度：medium
Solution: DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode flattenHelper(TreeNode root) {
if(root.left == null && root.right == null) {
return root;
} else if(root.left == null && root.right != null) {
return flattenHelper(root.right);
} else if(root.left != null && root.right == null) {
root.right = root.left;
root.left = null;
return flattenHelper(root.right);
} else {
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
TreeNode leftEnd = flattenHelper(root.right);
leftEnd.right = temp;
return flattenHelper(temp);
}
}
public void flatten(TreeNode root) {
if(root == null) {
return;
}
flattenHelper(root);
}
}