In Order ( Left, Root, Right)
Binary Tree Inorder Traversal
recursive way
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in ArrayList which contains node values.
*/
public ArrayList<Integer> inorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> res = new ArrayList<Integer>();
helper(res,root);
return res;
}
public void helper(List<Integer> res,TreeNode root){
if(root == null)return;
helper(res,root.left);
res.add(root.val);
helper(res,root.right);
}
}
Iterative Way
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack();
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
}
98. Validate Binary Search Tree
A binary tree's in-order traversal must be increasing . In recursion,we keep a previous value in the parameter and set its initial value to null. If during the traversal process the sequence is not increasing (no equal) then return false. We can also do it in an iterative way
Recursive:
public class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> pre = new ArrayList();
//Add null as its initial
pre.add(null);
return helper(root,pre);
}
//In order : left,root,right
public boolean helper(TreeNode root,List<Integer> list){
if(root == null)return true;
boolean left = helper(root.left,list);
if(list.get(0)!=null && list.get(0) >= root.val)return false;
list.set(0,root.val);
boolean right = helper(root.right,list);
return left && right;
}
}
Iterative:
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)return true;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack();
while(root != null ||!stack.isEmpty()){
//push left
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val)return false;
pre = root;
root = root.right;
}
return true;
}
}
173. Binary Search Tree Iterator
本质上还是In order的Iterative Traversal 只是多了一个外部的Start TreeNode 记录每次访问到的节点
public class BSTIterator {
private TreeNode start;
private Stack<TreeNode> stack = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
start = root;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if(start!=null || !(stack.isEmpty())){
return true;
}
return false;
}
/** @return the next smallest number */
public int next() {
int res = 0;
//navigate all the way down to the left and in the meantime push to the stack, then pop off and push the right substree according to the node popped out.
while(start != null){
stack.push(start);
start = start.left;
}
TreeNode t = stack.pop();
res = t.val;
start = t.right;
return res;
}
}
Level Order Traversal(Layer by layer)
103. Binary Tree Zigzag Level Order Traversal
还是树 的Level Order BFS遍历 只不过加了一个层数是不是奇数偶数的判断 在特定的层数里我们用Stack实现翻转
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root){
List<List<Integer>> result = new ArrayList();
//Always check before add something to queue
if(root == null)return result;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
int level = 0;
while(!q.isEmpty()){
int size = q.size();
level++;
List<Integer> list = new ArrayList<Integer>();
//stack is used for reverse
Stack<Integer> stack = new Stack();
for(int i = 0;i < size;i++){
TreeNode cur = q.poll();
if(level%2 != 0){
list.add(cur.val);
}
else{
stack.push(cur.val);
}
if(cur.left!=null)q.offer(cur.left);
if(cur.right!=null)q.offer(cur.right);
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
result.add(list);
}
return result;
}
}
101. Symmetric Tree
Except for the usual recursion way of solving it we can perform bi-direction level order traversal and compare whether each step for each pair the value is the same or both are null.
/**
* 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 isSymmetric(TreeNode root) {
if(root == null)return true;
if(root.left == null && root.right == null)return true;
if(root.left == null || root.right == null)return false;
//level order traversal in different direction
LinkedList<TreeNode> q1 = new LinkedList<TreeNode>();
LinkedList<TreeNode> q2 = new LinkedList<TreeNode>();
q1.add(root.left);
q2.add(root.right);
while(!q1.isEmpty() && !q2.isEmpty())
{
TreeNode n1 = q1.poll();
TreeNode n2 = q2.poll();
if(n1.val != n2.val) return false;
if(n1.left == null && n2.right != null || n1.left != null && n2.right == null)return false;
if(n1.right == null && n2.left != null || n1.right != null && n2.left == null)return false;
//只有在一对都不是Null的情况下才加入Queue
if(n1.left != null && n2.right != null)
{
q1.add(n1.left);
q2.add(n2.right);
}
if(n1.right != null && n2.left != null)
{
q1.add(n1.right);
q2.add(n2.left);
}
}
return true;
}
}
Pre Order 根左右
Recursion:
//Version 1: Traverse
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
traverse(root, result);
return result;
}
// 把root为跟的preorder加入result里面
private void traverse(TreeNode root, ArrayList<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
traverse(root.left, result);
traverse(root.right, result);
}
}
Iteration: 用stack
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null)return res;
Stack<TreeNode> stack = new Stack();
TreeNode p = root;
while(!stack.isEmpty() || p!=null){
while(p!=null){
res.add(p.val);
stack.push(p);
p = p.left;
}
p = stack.pop();
p = p.right;
}
return res;
}
114. Flatten Binary Tree to Linked List
想法有两种 一个是发现实际上所形成的链表的顺序是PreOrder So we just need to keep a pointer to the pre traversed TreeNode in the pre order list and append the current one to the pre node's right ! Before that keep the right subnode pointer of the current node in case we wipe away the original right substree. Pass the object not the value!
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root){
List<TreeNode> list = new ArrayList();
list.add(null);
helper(root,list);
}
public void helper(TreeNode root,List<TreeNode> list){
if(root == null)return;
TreeNode right = root.right;
TreeNode pre = list.get(0);
//set the right node to be the current traversing node
//set the left node to be null!!
if(pre != null){
pre.right = root;
pre.left = null;
}
list.set(0,root);
helper(root.left,list);
helper(right,list);
}
}
Post Order Traversal 左右根
Recursion
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
helper(root, res);
return res;
}
private void helper(TreeNode root, ArrayList<Integer> res)
{
if(root == null)
return;
helper(root.left,res);
helper(root.right,res);
res.add(root.val);
}