Q1 In-order traversal of Btree
public class Solution {
public List<Integer> inOrder(TreeNode root) {
// Write your solution here.
List<Integer> seq = new ArrayList<Integer>\(\);
Deque<TreeNode> stack = new LinkedList<TreeNode>\(\);
TreeNode cur = root;
while\(cur != null \|\| !stack.isEmpty\(\)\){
if\(cur != null\){
stack.offerFirst\(cur\);
cur = cur.left;
}else{
cur = stack.pollFirst\(\);
seq.add\(cur.key\);
cur = cur.right;
}
}
return seq;
}
}
Q2 Pre-order Traversal of Btree
public class Solution {
public List<Integer> preOrder(TreeNode root) {
// Write your solution here.
List<Integer> seq = new ArrayList<Integer>\(\);
if\(root == null\) return seq;
Deque<TreeNode> stack = new LinkedList<TreeNode>\(\);
stack.offerFirst\(root\);
while\(!stack.isEmpty\(\)\){
TreeNode cur = stack.pollFirst\(\);
if\(cur.right != null\){
stack.offerFirst\(cur.right\);
}
if\(cur.left != null\){
stack.offerFirst\(cur.left\);
}
seq.add\(cur.key\);
}
return seq;
}
}
Q3 Post-order Traversal of Btree
public class Solution {
public List<Integer> postOrder(TreeNode root) {
// Write your solution here.
List<Integer> seq = new ArrayList<Integer>\(\);
if\(root == null\) return seq;
Deque<TreeNode> stack = new LinkedList<TreeNode>\(\);
stack.offerFirst\(root\);
while\(!stack.isEmpty\(\)\){
TreeNode cur = stack.pollFirst\(\);
seq.add\(cur.key\);
if\(cur.left != null\){
stack.offerFirst\(cur.left\);
}
if\(cur.right != null\){
stack.offerFirst\(cur.right\);
}
}
Collections.reverse\(seq\);
return seq;
}
}
Q4 Check if Btree is Balanced
public class Solution {
public boolean isBalanced(TreeNode root) {
// Write your solution here.
if\(root == null\) return true;
int leftHeight = Height\(root.left\);
int rightHeight = Height\(root.right\);
return isBalanced\(root.left \) && isBalanced\(root.right \) && \(Math.abs\(leftHeight - rightHeight\) <= 1\);
}
private int Height(TreeNode root){
if\(root == null\) return 0;
int left = Height\(root.left\);
int right = Height\(root.right\);
return Math.max\(left, right\) + 1;
}
}
Q5 Symmetric Binary Tree
//time O(nlogn); space O(logn) worstcase O(n)
public class Solution {
public boolean isSymmetric(TreeNode root) {
// Write your solution here.
if\( root == null\) return true;
return isSymmetric\(root.left, root.right\);
}
private boolean isSymmetric(TreeNode a, TreeNode b){
if\(a == null && b == null\) return true;
if\(a == null \|\| b == null\) return false;
if\(a.key != b.key\) return false;
return isSymmetric\(a.left, b.right\) && isSymmetric\(a.right, b.left\);
}
}
Q6 Tweaked identical btree
// time:O(n*n),level = logn, function call:(n/2)^2 on average: 4^logn -> n^2
// space: O(height)
public class Solution {
public boolean isTweakedIdentical(TreeNode one, TreeNode two) {
// Write your solution here.
if\(one == null && two == null\) return true;
if\(one == null \|\| two == null\) return false;
if\(one.key != two.key\) return false;
// case1: if two nodes are not twisted
//case2: two nodes twisted
return \(isTweakedIdentical\(one.left, two.left\) && isTweakedIdentical\(one.right, two.right\)\) \|\|\(isTweakedIdentical\(one.left,two.right\) && isTweakedIdentical\(one.right, two.left\)\);
}
}
Q7 Is Binary Search Tree Or Not
// time O(n） space:O(n)
public class Solution {
public boolean isBST(TreeNode root) {
// Write your solution here.
return isBST\(root, Integer.MIN\_VALUE , Integer.MAX\_VALUE\);
}
private boolean isBST(TreeNode root, int min, int max){
if\(root == null\) return true;
if\(root.key < min \|\| root.key > max\) return false;
return isBST\(root.left, min, root.key - 1\) && isBST\(root.right, root.key + 1, max\);
}
}
//in order travesal solution
/*
public class Solution {
int last = Integer.MIN\_VALUE;
public boolean isBST\(TreeNode root\){
if\(root == null\) return true;
if\(!isBST\(root.left\)\) return false;
if\(root.key <= last\) return false;
last = root.key;
return isBST\(root.right\);
}
}
*/
Q8 Get Keys In Binary Search tree In given Range
// time: space:
public class Solution {
public List<Integer> getRange(TreeNode root, int min, int max) {
// Write your solution here.
List<Integer> res = new ArrayList<>\(\);
helper\(root, min, max, res\);
return res;
}
private void helper(TreeNode root, int min, int max, List<Integer> res){
if\(root == null\) return;
if\(root.key >= min\){
helper\(root.left, min, max, res\);
}
if\(min <= root.key && max >= root.key\){
res.add\(root.key\);
}
if\(root.key <= max\){
helper\(root.right, min, max, res\);
}
}
}