- Binary Tree Inorder Traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> list) {
if(root == null) {
return;
}
helper(root.left, list);
list.add(root.val);
helper(root.right, list);
}
}
- Binary Tree Preorder Traversal
class Solution {
// root left right
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorderTraversalHelper(root, result);
return result;
}
private List<Integer> preorderTraversalHelper(TreeNode node, List<Integer> list) {
if (node == null) {
return list;
}
list.add(node.val);
preorderTraversalHelper(node.left, list);
preorderTraversalHelper(node.right, list);
return list;
}
}
- Kth Smallest Element in a BST
class Solution {
int value = Integer.MAX_VALUE;
int idx = 0;
public int kthSmallest(TreeNode root, int k) {
if (root == null) return -1;
findKthSmallest(root, k);
if (idx == k)
return value;
return -1;
}
int findKthSmallest(TreeNode root, int k) {
if (root.left != null) {
int left = findKthSmallest(root.left, k);
if (left == k) return left;
}
idx++;
if (idx == k) {
value = root.val;
return idx;
}
if (root.right != null)
return findKthSmallest(root.right, k);
else return idx;
}
}
- Binary Search Tree Iterator
public class BSTIterator {
private TreeNode root;
public BSTIterator(TreeNode root) {
this.root = root;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return root != null;
}
/** @return the next smallest number */
public int next() {
if (root == null) {
return -1;
}
int ans = 0;
while (root != null) {
if (root.left == null) {
ans = root.val;
root = root.right;
break;
} else {
TreeNode tmp = root.left;
while (tmp.right != null && tmp.right != root) {
tmp = tmp.right;
}
if (tmp.right == null) {
tmp.right = root;
root = root.left;
} else {
ans = root.val;
tmp.right = null;
root = root.right;
break;
}
}
}
return ans;
}
}
- Binary Tree Level Order Traversal
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
/** List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
q.offer(null);
while(!q.isEmpty() && q.peek()!= null){
List<Integer> temp = new ArrayList<>();
TreeNode p = q.poll();
while(p != null){
temp.add(p.val);
if(p.left != null)
q.offer(p.left);
if(p.right != null)
q.offer(p.right);
p = q.poll();
}
res.add(temp);
q.offer(null);
}
return res;*/
List<List<Integer>> res = new ArrayList<>();
if(root == null)
return res;
helper(res,root,0);
return res;
}
private void helper(List<List<Integer>> res, TreeNode root, int level){
if(root == null)
return;
if(level >= res.size())res.add(new ArrayList<Integer>());
res.get(level).add(root.val);
helper(res,root.left,level+1);
helper(res,root.right,level+1);
}
}
- Binary Tree Right Side View
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
getRightView(root, 0, result);
return result;
}
public void getRightView(TreeNode root, int currentDepth, List<Integer> result){
if(root==null)
return;
if(currentDepth == result.size()){
result.add(root.val);
}
getRightView(root.right, currentDepth + 1, result);
getRightView(root.left, currentDepth + 1, result);
}
}
- Unique Binary Search Trees
class Solution {
public int numTrees(int n) {
if(n <= 0) return 0;
int[] res = new int[n + 1];
res[0] = 1;
res[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 0; j < i; j++){
res[i] += res[j] * res[i - j - 1];
}
}
return res[n];
}
}
- Populating Next Right Pointers in Each Node
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return ;
if (root.left != null) {
root.left.next = root.right;
}
if (root.right != null) {
if (root.next != null) {
root.right.next = root.next.left;
}
else { // root.next == null
root.right.next = null;
}
}
connect(root.left);
connect(root.right);
}
}
- Binary Tree Zigzag Level Order Traversal
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
helper(res,root,1);
return res;
}
public void helper(List<List<Integer>> res, TreeNode node,int lvl){
if(node==null) return;
if(lvl>res.size()){
List<Integer> newlist = new ArrayList<>();
newlist.add(node.val);
res.add(newlist);
}
else{
if(lvl%2==0) res.get(lvl-1).add(0,node.val);
else res.get(lvl-1).add(node.val);
}
helper(res,node.left,lvl+1);
helper(res,node.right,lvl+1);
}
}
- Flatten Binary Tree to Linked List
class Solution {
private TreeNode last = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (last != null) {
last.left = null;
last.right = root;
}
last = root;
TreeNode right = root.right;
flatten(root.left);
flatten(right);
}
}
public class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
if(root.left != null){
flatten(root.left);
TreeNode cur = root;
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
while(cur.right != null) cur = cur.right;
cur.right = temp;
flatten(temp);
}
else{
flatten(root.right);
}
}
}
- Path Sum II
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
List<Integer> temp = new ArrayList<>();
helper(root, sum, temp, res);
return res;
}
private void helper(TreeNode root, int sum, List<Integer> temp, List<List<Integer>> res) {
if(root == null) return;
else if (root.val == sum && root.left == null && root.right == null) {
temp.add(root.val);
res.add(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
return;
}else
temp.add(root.val);
helper(root.left, sum - root.val, temp, res);
helper(root.right, sum - root.val, temp, res);
temp.remove(temp.size() - 1);
}
}
- Construct Binary Tree from Preorder and Inorder Traversal
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,0,inorder,inorder.length-1,0);
}
private TreeNode buildTree(int[] preorder,int p,int[] inorder,int start,int end){
if(start<end || p>preorder.length-1)
return null;
int val = preorder[p];
int index = start;
for(int i=start;i>=end;i--){
if(val==inorder[i]){
index = i;
break;
}
}
TreeNode node = new TreeNode(val);
node.left = buildTree(preorder,p+1,inorder,index-1,end);
node.right = buildTree(preorder,p+(index-end)+1,inorder,start,index+1);
return node;
}
}
- Populating Next Right Pointers in Each Node II
public class Solution {
public void connect(TreeLinkNode root) {
while (root != null) {
TreeLinkNode current = root;
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode p = dummy;
while (current != null) {
if (current.left != null) {
p.next = current.left;
p = p.next;
}
if (current.right != null) {
p.next = current.right;
p = p.next;
}
current = current.next;
}
root = dummy.next;
}
}
}
- Construct Binary Tree from Inorder and Postorder Traversal
class Solution {
int p_inorder;
int p_postorder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
p_inorder = inorder.length - 1;
p_postorder = postorder.length-1;
return helper(inorder, postorder, null);
}
public TreeNode helper(int[] inorder, int[] postorder, TreeNode end){
if(p_postorder < 0){
return null;
}
TreeNode root = new TreeNode(postorder[p_postorder--]);
if(inorder[p_inorder] != root.val){
root.right = helper(inorder,postorder,root);
}
p_inorder--;
if((end == null) || (inorder[p_inorder] != end.val)){
root.left = helper(inorder,postorder,end);
}
return root;
}
}
- Lowest Common Ancestor of a Binary Tree
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
// BFS, map<curr, parent>, common ancestor must be p or q or one of their parent
public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
Map<TreeNode, TreeNode> map = new HashMap<>();
Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode tmp = queue.poll();
if (tmp.left != null) {
map.put(tmp.left, tmp);
queue.offer(tmp.left);
}
if (tmp.right != null) {
map.put(tmp.right, tmp);
queue.offer(tmp.right);
}
}
Set<TreeNode> set = new HashSet<>();
while (p != null) {
set.add(p);
p = map.get(p);
}
while (!set.contains(q)) {
q = map.get(q);
}
return q;
}
}
- Count Complete Tree Nodes
public class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
int count=1;
while(!q.isEmpty()){
TreeNode temp = q.poll();
if(temp.val!=-100){
temp.val=-100;
if(temp.left!=null){
q.offer(temp.left);
count++;
}
if(temp.right!=null){
q.offer(temp.right);
count++;
}
}
}
return count;
}
}
- Validate Binary Search Tree
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean helper(TreeNode root, long min, long max){
if(root == null)
return true;
if(root.val >= max || root.val <= min)
return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
}
