Minimum Depth of Binary Tree
public class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int lh = minDepth(root.left);
int rh = minDepth(root.right);
return (lh==0 || rh==0)?lh+rh+1:Math.min(lh,rh)+1;
}
}
Maxmum Depth of Binary Tree
class Solution {
public:
int dep = 0;
int maxDepth(TreeNode* root) {
dep = dfs(root);
return dep;
}
int dfs(TreeNode* root){
if(root == NULL) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
return 1+max(left,right);
}
};
Binary Tree Maximum Path Sum
public class Solution {
int maxValue;
public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}
private int maxPathDown(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, maxPathDown(node.left));
int right = Math.max(0, maxPathDown(node.right));
maxValue = Math.max(maxValue, left + right + node.val);
return Math.max(left, right) + node.val;
}
}
Sum Root to Leaf Numbers
public class Solution {
public int sumNumbers(TreeNode root) {
return sum(root, 0);
}
public int sum(TreeNode n, int s){
if (n == null) return 0;
if (n.right == null && n.left == null) return s*10 + n.val;
return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);
}
}
Binary Tree Paths
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> rst = new ArrayList<String>();
if(root == null) return rst;
StringBuilder sb = new StringBuilder();
helper(rst, sb, root);
return rst;
}
public void helper(List<String> rst, StringBuilder sb, TreeNode root){
if(root == null) return;
int tmp = sb.length();
if(root.left == null && root.right == null){
sb.append(root.val);
rst.add(sb.toString());
sb.delete(tmp , sb.length());
return;
}
sb.append(root.val + "->");
helper(rst, sb, root.left);
helper(rst, sb, root.right);
sb.delete(tmp , sb.length());
return;
}
}
Binary Tree Right Side View
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
q.addLast(root);
while(!q.isEmpty()){
int tmp = q.size();
TreeNode tmpNode ;
for(int i=1;i<=tmp;i++){
tmpNode = q.getFirst();
q.removeFirst();
if(i == tmp){
res.add(tmpNode.val);
}
if(tmpNode.left!=null) q.addLast(tmpNode.left);
if(tmpNode.right!=null) q.addLast(tmpNode.right);
}
}
return res;
}
}
Path Sum I
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (sum - root.val == 0 && root.left == null && root.right == null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
Path Sum II
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> cur = new ArrayList<Integer>();
help(root,sum,0,res,cur);
return res;
}
public void help(TreeNode p, int sum,int curSum,List<List<Integer>> res,List<Integer> curList){
if(p==null) return;
curList.add(p.val);
if(curSum+p.val == sum && p.left==null && p.right==null){
res.add(new ArrayList(curList));
curList.remove(curList.size()-1);
return;
}else{
help(p.left,sum,curSum+p.val,res,curList);
help(p.right,sum,curSum+p.val,res,curList);
}
curList.remove(curList.size()-1);
return;
}
}
Kth Smallest Element in a BST
public class Solution {
public int kthSmallest(TreeNode root, int k) {
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
int cnt = 0;
TreeNode p = root;
while(!s.isEmpty() || p!=null){
if(p!=null){
s.addFirst(p);
p = p.left;
}else{
p = s.getFirst();
s.removeFirst();
cnt++;
if(cnt==k){return p.val;}
p = p.right;
}
}
return 0;
}
}
Unique Binary Search Trees
public class Solution {
public int numTrees(int n) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,1);
map.put(1,1);
return numTrees(n, map);
}
private int numTrees(int n, Map<Integer, Integer> map){
// check memory
if(map.containsKey(n)) return map.get(n);
// recursion
int sum = 0;
for(int i = 1;i <= n;i++)
sum += numTrees(i-1, map) * numTrees(n-i, map);
map.put(n, sum);
return sum;
}
}
Unique Binary Search Trees II
public class Solution {
public List<TreeNode> generateTrees(int n) {
// DP, compute and store trees for intermediate ranges from 1 to n
// time: exponential, since for each range the number of trees is combinatorial
// space: O(n^2)
if (n == 0) {
List<TreeNode> result = new ArrayList<TreeNode>();
//result.add(null);
return result;
}
List<TreeNode>[][] treesForRange = (ArrayList<TreeNode>[][]) new ArrayList[n+2][n+1];
for (int step = 0; step < n; step++) {
for (int i = 1; i <= n - step; i++) {
int j = i + step;
treesForRange[i][j] = new ArrayList<TreeNode>();
if (step == 0) {
treesForRange[i][j].add(new TreeNode(i));
continue;
}
// k is a possible root for range i-j
for (int k = i; k <= j; k++) {
// two ugly if blocks for boundary cases:
// when k == i, the left subtree is null
// when k == j, the right subtree is null
if (treesForRange[i][k-1] == null) {
treesForRange[i][k-1] = new ArrayList<TreeNode>();
treesForRange[i][k-1].add(null);
}
if (treesForRange[k+1][j] == null) {
treesForRange[k+1][j] = new ArrayList<TreeNode>();
treesForRange[k+1][j].add(null);
}
for (TreeNode leftNode : treesForRange[i][k-1]) {
for (TreeNode rightNode : treesForRange[k+1][j]) {
TreeNode root = new TreeNode(k);
root.left = leftNode;
root.right = rightNode;
treesForRange[i][j].add(root);
}
}
}
}
}
return treesForRange[1][n];
}
}