package Tree; import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
class ListNode {
int val;
ListNode next; ListNode(int x) {
val = x;
}
}
class TreeLinkNode {
int val;
TreeLinkNode left, right, next; TreeLinkNode(int x) {
val = x;
}
}
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
public class TreeProblems {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeLinkNode a1 = new TreeLinkNode(1);
TreeLinkNode a2 = new TreeLinkNode(2);
TreeLinkNode a3 = new TreeLinkNode(3);
TreeLinkNode a4 = new TreeLinkNode(4);
TreeLinkNode a5 = new TreeLinkNode(5);
TreeLinkNode a6 = new TreeLinkNode(6);
TreeLinkNode a7 = new TreeLinkNode(7);
a1.left = a2;
a1.right = a3;
a2.left = a4;
a2.right = a5;
a3.left = a6;
a3.right = a7;
System.out.println(a5.next.val);
TreeNode aaa1 = new TreeNode(4);
TreeNode aaa2 = new TreeNode(1);
TreeNode aaa3 = new TreeNode(2);
TreeNode aaa4 = new TreeNode(3);
aaa1.left = aaa2;
aaa2.left = aaa3;
aaa3.left = aaa4;
/*
* 9 5 13 1 7 10
*/
TreeNode aa1 = new TreeNode(5);
TreeNode aa2 = new TreeNode(4);
TreeNode aa3 = new TreeNode(8);
TreeNode aa4 = new TreeNode(11);
TreeNode aa5 = new TreeNode(13);
TreeNode aa6 = new TreeNode(4);
TreeNode aa7 = new TreeNode(7);
TreeNode aa8 = new TreeNode(2);
TreeNode aa9 = new TreeNode(1);
aa1.left = aa2;
aa1.right = aa3;
aa2.left = aa4;
aa3.left = aa5;
aa3.right = aa6;
aa4.left = aa7;
aa4.right = aa8;
aa6.right = aa9;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//树的问题很多都是dfs的问题，首先要学会preorder，inorder，postorder三种dfs算法的两种实现方式。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* 94. Binary Tree Inorder Traversal
* 2015.11.21 By Mingyang
* 跟preorder一样的dfs，不过是每次pop出来的时候记在小本本上，也就是记在list里面 中序遍历迭代解法
* 用栈先把根节点的所有左孩子都添加到栈内， 然后输出栈顶元素，再处理栈顶元素的右子树
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode t = stack.pop();
list.add(t.val);
p = t.right;
}
}
return list;
}
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
dfs(root, res);
return res;
}
public void dfs(TreeNode root, List<Integer> res) {
if (root == null)
return;
dfs(root.left, res);
res.add(root.val);
dfs(root.right, res);
}
/*
* 144. Binary Tree Preorder Traversal
* 2015.11.21 By Mingyang
* 典型的dfs的做法，每次push进去一个值的时候就记在小本本上，其实也就是记在list里面
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
list.add(p.val);
p = p.left;
} else {
TreeNode t = stack.pop();
p = t.right;
}
}
return list;
}
public List<Integer> preorderTraversal1(TreeNode root) {
List<Integer> res=new ArrayList<Integer>();
dfs(res,root);
return res;
}
public void dfs(List<Integer> res,TreeNode root){
if(root==null)
return;
res.add(root.val);
dfs(res,root.left);
dfs(res,root.right);
}
/*
* 145. Binary Tree Postorder Traversal
* 2015.11.21 by Mingyang
* 左右中，反过来就是中左右，所以就相当于inorder反过来，稍稍改进一下就好
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
list.add(p.val);
p = p.right;
} else {
TreeNode t = stack.pop();
p = t.left;
}
}
Collections.reverse(list);
return list;
}
public List<Integer> postorderTraversal1(TreeNode root) {
List<Integer> res=new ArrayList<Integer>();
dfs(root,res);
return res;
}
public void dfs1(TreeNode root,List<Integer> res){
if(root==null)
return;
dfs1(root.left,res);
dfs1(root.right,res);
res.add(root.val);
}
/*
* 95. Unique Binary Search Trees II
* 2015.11.23 By Mingyang
* 分成两个函数来写，另外一个函数写满起点到终点
*/
public List<TreeNode> generateTrees(int n) {
return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> list = new LinkedList<TreeNode>();
if (start > end) {
list.add(null);
return list;
}
for (int i = start; i <= end; i++) {
List<TreeNode> lefts = generateTrees(start, i - 1);//以i作为根节点，左子树由[1,i-1]构成
List<TreeNode> rights = generateTrees(i + 1, end);//右子树由[i+1, n]构成
for (TreeNode left : lefts) {//左边和右边分别返回了一个list，每个值就是一个TreeNode，就代表一种可能性
for (TreeNode right : rights) {
TreeNode node = new TreeNode(i);
node.left = left;
node.right = right;
list.add(node);//存储所有可能行
}
}
}
return list;
}
/*
* 145. Binary Tree Postorder Traversal
* 上面的变体，给你一个preorder的array，看看是不是BST的preorder
* 2015.1.24 by Mingyang
*/
public static boolean canRepresentBST(int pre[], int n) {
// Create an empty stack
Stack<Integer> s = new Stack<Integer>();
// Initialize current root as minimum possible
// value
int root = Integer.MIN_VALUE;
// Traverse given array
for (int i = 0; i < n; i++) {
// If we find a node who is on right side
// and smaller than root, return false
if (pre[i] < root) {
return false;
}
// If pre[i] is in right subtree of stack top,
// Keep removing items smaller than pre[i]
// and make the last removed item as new
// root.
while (!s.empty() && s.peek() < pre[i]) {
root = s.peek();
s.pop();
}
// At this point either stack is empty or
// pre[i] is smaller than root, push pre[i]
s.push(pre[i]);
}
return true;
}
/*
* 156.Binary Tree Upside Down
* 2016-3-26 by Mingyang
* For example:
*Given a binary tree {1,2,3,4,5},
1
/ \
2 3
/ \
4 5
*return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1
*先去处理最左下角的分支，因为他就是未来的root，然后再一层一层的上来
*/
public TreeNode UpsideDownBinaryTree(TreeNode root) {
if (root == null)
return null;
TreeNode parent = root, left = root.left, right = root.right;
if (left != null) {
TreeNode ret = UpsideDownBinaryTree(left);
left.left = right;
left.right = parent;
return ret;
}
return root;
}
/*
* 272.Closest Binary Search Tree Value II
* 2016-3-27 By Mingyang
* 二叉搜索树的中序遍历就是顺序输出二叉搜索树，所以我们只要中序遍历二叉搜索树，同时维护一个大小为K的队列，
* 前K个数直接加入队列，之后每来一个新的数（较大的数），如果该数和目标的差，相比于队头的数离目标的差来说，
* 更小，则将队头拿出来，将新数加入队列。如果该数的差更大，则直接退出并返回这个队列，因为后面的数更大，差值也只会更大。
* @return true if result is already found.
*/
public List<Integer> closestKValues(TreeNode root, double target, int k) {
LinkedList<Integer> list = new LinkedList<Integer>();
closestKValuesHelper(list, root, target, k);
return list;
}
private boolean closestKValuesHelper(LinkedList<Integer> list,TreeNode root, double target, int k) {
if (root == null) {
return false;
}
if (closestKValuesHelper(list, root.left, target, k)) {
return true;
}
if (list.size() == k) {
if (Math.abs(list.getFirst() - target) < Math.abs(root.val - target)) {
return true;
} else {
list.removeFirst();
}
}
list.addLast(root.val);
return closestKValuesHelper(list, root.right, target, k);
}
/*
* 270 Closest Binary Search Tree Value
* Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
* 2016-3-26 by Mingyang
* 其实很简单，就是在dfs的过程中不断的缩小范围，没到一个点就开始去update最小的距离
*/
public int closestValue3(TreeNode root, double target) {
int closest = root.val;
while (root != null) {
// 如果该节点的离目标更近，则更新到目前为止的最近值
closest = Math.abs(closest - target) < Math.abs(root.val - target) ? closest: root.val;
// 二叉搜索
root = target < root.val ? root.left : root.right;
}
return closest;
}
/*
* 265.Count Univalue Subtrees
* 2016-3-26 by Mingyang
* Given a binary tree, count the number of uni-value subtrees.
* A Uni-value subtree means all nodes of the subtree have the same value.
* 这里是自底向上的模式，
*/
private int count = 0;
public int countUnivalSubtrees(TreeNode root) {
unival(root);
return count;
}
private boolean unival(TreeNode root) {
if (root == null)
return true;
if (root.left == null && root.right == null) {
count++;
return true;
}
boolean left = unival(root.left);//自底向上第一步，走到最底的那一层
boolean right = unival(root.right);
if (left && right && (root.left == null || root.left.val == root.val)&& (root.right == null || root.right.val == root.val)) {
count++;
return true;
}
return false;
}
/*
* 285.Inorder Successor in BST
* 11.21 By Mingyang
* Case1: Node has right subtree: Go deep to leftmost node in right subtree or find min in right subtree
* Case2:No right subtree:1.go back to parent from left, parent is successor,and parent is unvisited
* 2.from right, parent already visited, we need on more further
* ---Go to the nearest ancestor for which given node would be in left subtree
*/
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Stack<TreeNode> stk = new Stack<TreeNode>();
TreeNode curr = root;
// 找到目标节点并把路径上的节点压入栈,也就是首先找到这个节点，大概时间是logn
while(curr != p){
stk.push(curr);
if(curr.val > p.val){
curr = curr.left;
} else {
curr = curr.right;
}
}
// 如果目标节点有右节点，则找到其右节点的最左边的节点，就是下一个数
if(curr.right != null){
curr = curr.right;
while(curr.left != null){
curr = curr.left;
}
return curr;
} else {
// 如果没有右节点，pop栈找到第一个比目标节点大的节点。因为如果目标没有右节点，那么就看他从左边还是右边回到父亲，如果从左边回到父亲，父亲就是下一个
//如果不是，go to the nearest ancestor for which given node would be in left subtree
while(!stk.isEmpty() && stk.peek().val < curr.val){
stk.pop();
}
// 如果栈都pop空了还没有比目标节点大的，说明没有更大的了
return stk.isEmpty() ? null : stk.pop();
}
}
/*
* 255.Verify Preorder Sequence in Binary Search Tree
* Given an array of numbers,
* verify whether it is the correct preorder traversal sequence of a binary
* search tree.
* 11.21 By Mingyang
* Time complexity O(n^2), space complexity O(1).
*/
public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length <= 1) {
return true;
}
return dfs(preorder, 0, preorder.length - 1);
}
private boolean dfs(int[] preorder, int low, int hi) {
if (low >= hi) {
return true;
}
int root = preorder[low];
int i = low + 1;
while (i <= hi && preorder[i] < root) {
i++;
}
int j = i;
while (j <= hi && preorder[j] > root) {
j++;
}
if (j <= hi) {
return false;
}
return dfs(preorder, low + 1, i - 1) && dfs(preorder, i, hi);
}
/*
* 103. Binary Tree Zigzag Level Order Traversal
* 11.21 By Mingyang
*/
public static ArrayList<ArrayList<Integer>> zigzagLevelOrder2(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if (root == null)
return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int num = 0;
boolean reverse = false;// a flag
while (!queue.isEmpty()) {
num = queue.size();
ArrayList<Integer> levelres = new ArrayList<Integer>();
for (int i = 0; i < num; i++) {
TreeNode node = queue.poll();
levelres.add(node.val);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
if (reverse) {
Collections.reverse(levelres);
reverse = false;
} else {
reverse = true;
}
res.add(levelres);
}
return res;
}
/*
* 107. Binary Tree Level Order Traversal II 11.21 By Mingyang I的解答加一行：
* Collections.reverse(results);就好了
*/
/*
* 102. Binary Tree Level Order Traversal
* 11.21 by Mingyang 最基本的queue的做法
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return results;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int currentNumber = 1;
int nextNumber = 0;
while (queue.size() != 0) {
TreeNode temp = queue.poll();
result.add(temp.val);
currentNumber--;
if (temp.left != null) {
queue.add(temp.left);
nextNumber++;
}
if (temp.right != null) {
queue.add(temp.right);
nextNumber++;
}
if (currentNumber == 0) {
results.add(result);
currentNumber = nextNumber;
nextNumber = 0;
result = new ArrayList<Integer>();
}
}
return results;
}
/*
* 222.Count Complete Tree Nodes
* 11.20 By Mingyang
* 最先各自计算最左边那一束到底的长度，再计算右边到底的长度，如果相等，ok，# of nodes = 2^h -1（计算满树很简单的！）
* 若不相等，再继续迭代，这样做节省了很多时间
* T(n)=logn+2T(n/2)，最后算出来就是n，其实可以这么理解，每个节点都只是访问了一次，所以还是n。注意树的高度是logn
*/
public int countNodes(TreeNode root) {
if (root == null)
return 0;
int leftHeight = 1, rightHeight = 1;
// 计算左子树
TreeNode temp = root.left;
while (temp != null) {
temp = temp.left;
leftHeight++;
}
// 计算右子树
temp = root.right;
while (temp != null) {
temp = temp.right;
rightHeight++;
}
if (leftHeight == rightHeight)
return (1 << leftHeight) - 1;
// 也可以：(2<<(left-1))-1，这里h是left-1
return countNodes(root.left) + countNodes(root.right) + 1;
}
/*
* 226. Invert Binary Tree
* 11.19 By Mingyang
*/
public TreeNode invertTree(TreeNode root){
exchange(root);
return root;
}
public void exchange(TreeNode root) {
if(root==null)
return;
if(root.left==null&&root.right==null)
return;
TreeNode Temp=root.left;
root.left=root.right;
root.right=Temp;
exchange(root.left);
exchange(root.right);
}
/*
* 230.Kth Smallest Element in a BST
* 11.19 By Mingyang
*/
private static int number = 0;
private static int county = 0;
public int kthSmallest1(TreeNode root, int k) {
county = k;
dfs(root);
return number;
}
public void dfs(TreeNode root) {
if (root == null)
return;
dfs(root.left);
county--;
if (county == 0) {
number = root.val;
return;
}
dfs(root.right);
}
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
int result = 0;
// 不断的dfs，利用左中右的遍历方式进行遍历，然后依次取到最后的值
while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode t = stack.pop();
k--;
if (k == 0)
result = t.val;
p = t.right;
}
}
return result;
}
// 我的方法更快,利用左子树和右字数的个数的关系，如果k大于左子树的个数，那么就可以往右边走，这种方法复杂度T(n)=2T(n/2)+logn,也就是n
//这里用了Binary Search的方法，根据count的大小来判断在哪个区间，然后去那个区间search，所以按理来说应该是logn，可是因为count用了n，所以总的时间就是n，哈哈！
public int kthSmallest2(TreeNode root, int k) {
int count = countNodes2(root.left);
if (k <= count) {
return kthSmallest2(root.left, k);
} else if (k > count + 1) {
return kthSmallest2(root.right, k-1-count); // 1 is counted as current node
}
return root.val;
}
public int countNodes2(TreeNode n) {
if (n == null) return 0; return 1 + countNodes2(n.left) + countNodes2(n.right);
}
/*
* 235. Lowest Common Ancestor of a Binary Search Tree
* 11.19 By Mingyang
* 这题目更简单，下面两种方法都适用，现在给出更直接的方法
*/
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
if (p.val == root.val || q.val == root.val)
return root;
if ((p.val < root.val && q.val > root.val)|| (p.val > root.val && q.val < root.val))
return root;
if (p.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else {
return lowestCommonAncestor(root.right, p, q);
}
}
/*
* 236. Lowest Common Ancestor of a Binary Tree
* 11.19 By Mingyang
* 这道题目比BST更难，不过这道题目的答案可以通用的
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 发现目标节点则通过返回值标记该子树发现了某个目标结点
if (root == null || root == p || root == q)
return root;
// 查看左子树中是否有目标结点，没有为null
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 查看右子树是否有目标节点，没有为null
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 都不为空，说明做右子树都有目标结点，则公共祖先就是本身
if (left != null && right != null)
return root;
// 如果发现了目标节点，则继续向上标记为该目标节点
return left == null ? right : left;
}
/*
* 298 Binary Tree Longest Consecutive Sequence
* 2016-3-27 by Mingyang
* The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections.
* The longest consecutive path need to be from parent to child (cannot be the reverse).
*/
private int result = Integer.MIN_VALUE;
public int longestConsecutive(TreeNode root) {
if(root == null)
return 0;
dfs(root, 0, root);
return result;
}
private void dfs(TreeNode root, int cur, TreeNode pre) {
if(root == null)
return;
if(root.val == pre.val+1)
cur++;
else
cur = 1;
result = Math.max(result, cur);
dfs(root.left, cur, root);
dfs(root.right, cur, root);
}
/*
* 333.Largest BST Subtree
* 2016-3-27 by Mingyang
* Given a binary tree, find the largest subtree which is a Binary Search Tree (BST)
* where largest means subtree with largest number of nodes in it.
* why not traverse up the tree using a bottom-up approach?
* In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.
* Using a bottom-up approach, we need to pass some information up the tree.
* Obviously, we need to pass minimum and maximum values of the subtree as we traverse up the tree, so the above subtrees could be verified for BST’s properties
* 自底向上的方法，不过需要存lower，upper的值以及size的大小
*/
class Result { // (size, rangeLower, rangeUpper) -- size of current tree, range of current tree [rangeLower, rangeUpper]
int size;
int lower;
int upper;
Result(int size, int lower, int upper) {
this.size = size;
this.lower = lower;
this.upper = upper;
}
}
int max = 0;
public int largestBSTSubtree(TreeNode root) {
if (root == null) { return 0; }
traverse(root, null);
return max;
}
private Result traverse(TreeNode root, TreeNode parent) {
if (root == null) { return new Result(0, parent.val, parent.val); }
Result left = traverse(root.left, root);
Result right = traverse(root.right, root);
if (left.size==-1 || right.size==-1 || root.val<left.upper || root.val>right.lower) {
return new Result(-1, 0, 0);
}
int size = left.size + 1 + right.size;
max = Math.max(size, max);
return new Result(size, left.lower, right.upper);//更新新的BST的范围，新的Size
}
}
/*
* 297. Serialize and Deserialize Binary Tree
* 2016-3-27 by Mingyang
*/
class Codec {
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}
private void buildString(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
} else {
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<String>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}
private TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(NN)) return null;
else {
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}
}