Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values. Note: Recursive solution is trivial, could you do it iteratively?
难度：medium
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 List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Stack<TreeNode> nodes = new Stack<>();
nodes.push(root);
while(!nodes.empty()) {
TreeNode curRoot = nodes.pop();
res.add(curRoot.val);
if(curRoot.right != null) {
nodes.push(curRoot.right);
}
if(curRoot.left != null) {
nodes.push(curRoot.left);
}
}
return res;
}
}
Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values. Note: Recursive solution is trivial, could you do it iteratively?
难度：hard
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 List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Stack<TreeNode> nodes = new Stack<>();
nodes.add(root);
while(!nodes.empty()) {
TreeNode cur = nodes.peek();
if(cur.left == null && cur.right == null) {
res.add(cur.val);
nodes.pop();
}
if(cur.right != null) {
nodes.push(cur.right);
cur.right = null;
}
if(cur.left != null) {
nodes.push(cur.left);
cur.left = null;
}
}
return res;
}
}
另一种思路是用LinkedList来存结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}
Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
难度：medium
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 List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Stack<TreeNode> nodes = new Stack<>();
nodes.add(root);
while(!nodes.empty()) {
TreeNode cur = nodes.peek();
if(cur.left != null) {
nodes.push(cur.left);
cur.left = null;
} else {
res.add(cur.val);
nodes.pop();
if(cur.right != null) {
nodes.push(cur.right);
}
}
}
return res;
}
}
Solution: Morris Traversal
Threaded Binary Tree
A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.
步骤：
如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
TreeNode curRoot = root;
TreeNode pre = null;
while(curRoot != null) {
if(curRoot.left == null) { // 1
res.add(curRoot.val);
curRoot = curRoot.right;
} else {
pre = curRoot.left;
while(pre.right != null && pre.right != curRoot) {
pre = pre.right;
}
if(pre.right == null) { // 2.a)
pre.right = curRoot;
curRoot = curRoot.left;
}
if(pre.right == curRoot) { // 2.b)
pre.right = null;
res.add(curRoot.val);
curRoot = curRoot.right;
}
}
}
return res;
}
}
Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
难度：medium
Solution: Recursive
这个方法不能用来recover BST，因为会错过root节点是乱序的情况。
/**
* 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 isValidBST(TreeNode root) {
return isValidBSTHelper(root, null, null);
}
private boolean isValidBSTHelper(TreeNode root, TreeNode leftBound, TreeNode rightBound) {
if(root == null) {
return true;
}
if((leftBound == null || root.val > leftBound.val) && (rightBound == null || root.val < rightBound.val)) {
return isValidBSTHelper(root.left, leftBound, root) && isValidBSTHelper(root.right, root, rightBound);
}
return false;
}
}
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
难度：hard
这道题的本质是inorder traversal和out-of-order detection。所有用到stack的解法都是空间复杂度的解法。所以要实现只能用Morris Traversal。
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 {
class TraverseResult {
TreeNode node;
TreeNode bound;
TraverseResult(TreeNode n1, TreeNode n2) {
node = n1;
bound = n2;
}
}
public void recoverTree(TreeNode root) {
if(root == null) {
return;
}
TraverseResult greater = inorderTraverse(root, null);
TraverseResult smaller = reverseTraverse(root, null);
int temp = greater.node.val;
greater.node.val = smaller.node.val;
smaller.node.val = temp;
}
private TraverseResult inorderTraverse(TreeNode root, TreeNode bound) {
if(root.left != null) {
TraverseResult left = inorderTraverse(root.left, bound);
if(left.node != null) {
return left;
}
bound = left.bound;
}
if(bound != null && root.val < bound.val) {
return new TraverseResult(bound, bound);
}
bound = root;
if(root.right != null) {
TraverseResult right = inorderTraverse(root.right, bound);
if(right.node != null) {
return right;
}
bound = right.bound;
}
return new TraverseResult(null, bound);
}
private TraverseResult reverseTraverse(TreeNode root, TreeNode bound) {
if(root.right != null) {
TraverseResult right = reverseTraverse(root.right, bound);
if(right.node != null) {
return right;
}
bound = right.bound;
}
if(bound != null && root.val > bound.val) {
return new TraverseResult(bound, bound);
}
bound = root;
if(root.left != null) {
TraverseResult left = reverseTraverse(root.left, bound);
if(left.node != null) {
return left;
}
bound = left.bound;
}
return new TraverseResult(null, bound);
}
}
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 void recoverTree(TreeNode root) {
TreeNode pre = null;
TreeNode first = null, second = null;
// Morris Traversal
TreeNode temp = null;
while(root != null) {
if(root.left != null) {
// connect threading for root
temp = root.left;
while(temp.right != null && temp.right != root) {
temp = temp.right;
}
// the threading already exists
if(temp.right != null) {
if(pre != null && pre.val > root.val) {
if(first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
temp.right = null;
root = root.right;
}else{
// construct the threading
temp.right = root;
root = root.left;
}
} else {
if(pre != null && pre.val > root.val) {
if(first == null) {
first = pre;
second = root;
} else {
second = root;
}
}
pre = root;
root = root.right;
}
}
// swap two node values;
if(first!= null && second != null) {
int t = first.val;
first.val = second.val;
second.val = t;
}
}
}
Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
难度：medium
Solution: BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
Queue<TreeNode> nextLevel = new LinkedList<>();
nextLevel.add(root);
while(!nextLevel.isEmpty()) {
List<Integer> tempRes = new ArrayList<>();
int qSize = nextLevel.size();
for(int i = 0; i < qSize; ++i) {
TreeNode cur = nextLevel.remove();
tempRes.add(cur.val);
if(cur.left != null) {
nextLevel.add(cur.left);
}
if(cur.right != null) {
nextLevel.add(cur.right);
}
}
res.add(tempRes);
}
return res;
}
}
Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
难度：easy
Solution: BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if(root == null) {
return res;
}
Queue<TreeNode> nextLevel = new LinkedList<>();
nextLevel.add(root);
while(!nextLevel.isEmpty()) {
int qSize = nextLevel.size();
List<Integer> tempRes = new LinkedList<>();
for(int i = 0; i < qSize; ++i) {
TreeNode cur = nextLevel.remove();
tempRes.add(cur.val);
if(cur.left != null) {
nextLevel.add(cur.left);
}
if(cur.right != null) {
nextLevel.add(cur.right);
}
}
res.add(0, tempRes);
}
return res;
}
}
Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
难度：medium
Solution: BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) {
return res;
}
Stack<TreeNode> curLevel = new Stack<>();
curLevel.push(root);
boolean leftFirst = true;
while(!curLevel.empty()) {
List<Integer> tempRes = new ArrayList<>();
Stack<TreeNode> nextLevel = new Stack<>();
while(!curLevel.empty()) {
TreeNode curRoot = curLevel.pop();
tempRes.add(curRoot.val);
if(leftFirst) {
if(curRoot.left != null) {
nextLevel.push(curRoot.left);
}
if(curRoot.right != null) {
nextLevel.push(curRoot.right);
}
} else {
if(curRoot.right != null) {
nextLevel.push(curRoot.right);
}
if(curRoot.left != null) {
nextLevel.push(curRoot.left);
}
}
}
leftFirst = !leftFirst;
curLevel = nextLevel;
res.add(tempRes);
}
return res;
}
}
Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
难度：medium
Solution: BFS
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null) {
return;
}
TreeLinkNode dummyHead = new TreeLinkNode(0);
dummyHead.next = root;
root.next = null;
TreeLinkNode ptr = dummyHead.next;
while(ptr != null) {
TreeLinkNode nextPtr = dummyHead;
while(ptr != null) {
if(ptr.left != null) {
nextPtr.next = ptr.left;
nextPtr = nextPtr.next;
}
if(ptr.right != null) {
nextPtr.next = ptr.right;
nextPtr = nextPtr.next;
}
ptr = ptr.next;
}
nextPtr.next = null;
ptr = dummyHead.next;
}
}
}
Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node". What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space.
Solution: BFS
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null) {
return;
}
TreeLinkNode dummyHead = new TreeLinkNode(0);
dummyHead.next = root;
root.next = null;
TreeLinkNode ptr = root, nextPtr = null;
while(ptr != null) {
nextPtr = dummyHead;
while(ptr != null) {
if(ptr.left != null) {
nextPtr.next = ptr.left;
nextPtr = nextPtr.next;
}
if(ptr.right != null) {
nextPtr.next = ptr.right;
nextPtr = nextPtr.next;
}
ptr = ptr.next;
}
nextPtr.next = null;
ptr = dummyHead.next;
}
}
}
Binary Search Tree Iterator
Medium
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Solution: Stack + Inorder traversal
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
Stack<TreeNode> parents;
public BSTIterator(TreeNode root) {
parents = new Stack<TreeNode>();
while(root != null) {
parents.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !parents.empty();
}
/** @return the next smallest number */
public int next() {
TreeNode cur = parents.pop();
TreeNode root = cur.right;
while(root != null) {
parents.push(root);
root = root.left;
}
return cur.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
Kth Smallest Element in a BST
Medium
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Solution: In-order traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class Result {
int k;
int val;
Result(int k, int val) {
this.k = k;
this.val = val;
}
}
public int kthSmallest(TreeNode root, int k) {
Result res = kthSmallestHelper(root, k);
return res.val;
}
private Result kthSmallestHelper(TreeNode root, int k) {
if(root == null) {
return new Result(k, 0);
}
Result L = kthSmallestHelper(root.left, k);
if(L.k == 0) {
return L;
} else if(L.k == 1) {
return new Result(0, root.val);
}
return kthSmallestHelper(root.right, L.k - 1);
}
}
Verify Preorder Serialization of a Binary Tree
Medium
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Solution: Stack
Note: there is another solution that doesn't use stack. Reference
class Solution {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int right = preorderTraverse(nodes, 0);
return right == nodes.length;
}
private int preorderTraverse(String[] nodes, int start) {
if(start >= nodes.length) {
return nodes.length + 1;
}
if(nodes[start].equals("#")) {
return start + 1;
}
int right = preorderTraverse(nodes, start + 1);
return preorderTraverse(nodes, right);
}
}