刷题记录

Analysis: Mirror problem of  Construct Binary Tree from Inorder and Preorder Traversal . Reverse of postorder is root -> right ->left. So start from the end of the postorder array. Have to be extremely careful when dealing with left and right of inorder array. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { Map<Integer, Integer> inMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { inMap.put(inorder[i], i); } return helper(postorder.length - 1, 0, inorder.length - 1, postorder, inMap); } private TreeNode helper(int postStart, int inStart, int inEnd, int[] postorder, Map<Integer, Integer> inMap) { if (inStart > i...

Problem: Given preorder and inorder traversal of a tree, construct the binary tree. Analysis: This problem takes me a while to understand the solution. Consider the binary tree below: preorder sequence is: 4,2,1,3,6,5,7 inorder sequence is: 1,2,3,4,5,6,7 We can find the root easily with preorder array. The root is 4 in preorder array, the left and right trees are [1,2,3] and [5,6,7] respectively.  Then construct the sub trees recursively. The root.left's root is easy to determine, it is located at preStart + 1. The right subtree's root is number of nodes in left subtree away from parent root. That is preStart + inIndex - inStart + 1. Use a hashmap to catch index of inorder array reduces time complexity to O(n). Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNod...

Problem: Given a binary search tree and a node in it, find the in-order successor of that node in the BST. Note : If the given node has no in-order successor in the tree, return  null . Analysis: 4/24/2018 update: It's BST version of binary search. class Solution { public TreeNode inorderSuccessor ( TreeNode root, TreeNode p) { TreeNode res = null; while (root != null) { if (root . val > p . val) { res = root; root = root . left; } else root = root . right; } return res; } } Create a flag, set to true if found p. If flag is true, the current node is the successor of p. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode inorderSuccessor(TreeNod...

Problem: 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. For example, Given the following binary tree, 1 / \ 2 3 / \ \ 4 5 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL 4/25/2018 update: The best approach of all is to use dummy node on each level. Then we won't worry about the prev and next. /** * 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) { while (root != null) { TreeLinkNode childHead = new TreeLi...

Problem: 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). For example, Given the following perfect binary tree, 1 / \ 2 3 / \ / \ 4 5 6 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL 4/24/2018 update: 这道题感觉iterative要好很多，没有什么递归的必要。 Iterative: public class Solution { public void connect ( TreeLinkNode root) { TreeLinkNode start = root; while...

Problem: 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). For example: Given binary tree  [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Analysis: Use a flag to mark whether to reverse or not. Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); Boolean reverse = false; if (root == null) return res; queue.offer(root); while (!queue.isEmpty()) {...

3/16/2018 update: Inorder and preorder should use the template as follows. Because the Binary Search Tree Iterator uses this template. public class Solution { public List < Integer > inorderTraversal ( TreeNode root) { List < Integer > res = new ArrayList < > (); Stack < TreeNode > stack = new Stack < > (); TreeNode curr = root; while (curr != null || ! stack . isEmpty()) { while (curr != null) { stack . push(curr); curr = curr . left; } curr = stack . pop(); res . add(curr . val); curr = curr . right; } return res; } } 2/24/218 update Preorder adds value when pushing, inorder adds value when popping. -------------------------------------------------------------------------------------------------- 1/9/2018 update Postorder iterative is too hard without reversing preorder. Need to memorize th...

思路： 递归版太简单了。迭代版需要用到stack，由于preorder 是root-> left -> right。所以stack push的顺序是反的。先检查right 是否为空，push right, 再处理left。