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; } } }