/** * 面试题27 输入一颗二叉树，输出一颗对称的二叉树 * 思路：从根结点开始，交换两个子结点 * * @param root */ public void mirror(TreeNode root) { if (root == null) return; TreeNode temp = root.left; root.left = root.right; root.right = temp; mirror(root.left); mirror(root.right); }
/** * 面试题28：判断输入二叉树是否是对称二叉树 * 思路：将前序遍历和前序对称遍历获取的结点值进行比较 * * @param root * @return */ public boolean isSym(TreeNode root) { //invalid input if (root == null) return false; return isSymCore(root, root); } private boolean isSymCore(TreeNode root1, TreeNode root2) { //递归结束条件 if (root1 == null && root2 == null) return true; if (root1 == null || root2 == null) return false; if (root1.val != root2.val) return false; //root1 and root2 是对称遍历 return isSymCore(root1.left, root2.right) && isSymCore(root1.right, root2.left); }
/** * 面试题30：含有O(1)min方法的栈 * 思路：建立一个辅助栈，该栈中栈顶元素始终是当前数据栈中的最小元素。 */ private Stack<Integer> dateStack = new Stack<>(); private Stack<Integer> minStack = new Stack<>(); public void push(int date) { //入栈的数据是当前最小值,注意minStack为空的情况 if (date < minStack.peek() || minStack.empty()) { minStack.push(date); } else minStack.push(minStack.peek()); dateStack.push(date); } public int pop() { minStack.pop();//栈为空时抛出异常 return dateStack.pop(); } public int min() { return minStack.peek(); }
/** * 面试题31：判断压入栈和弹出栈是否匹配 * 思路：建立一个辅助栈 * 当辅助栈顶元素值为空，或者与出栈序列不同时，入栈序列入栈 * 相同时，出栈序列出栈，辅助栈出栈 * * @param pushA * @param popA * @return */ public boolean IsPopOrder(int[] pushA, int[] popA) { //invalid input if (pushA == null || popA == null) return false; int pushALen = pushA.length; int popALen = popA.length; if (pushALen != popALen) return false; //匹配 int pushAptr = 0; int popAptr = 0; Stack<Integer> stack = new Stack<>(); while (popAptr != popALen) { if (stack.empty() || stack.peek() != popA[popAptr]) { if (pushAptr == pushALen) return false; else stack.push(pushA[pushAptr++]); } else { stack.pop(); ++popAptr; } } return true; }
/** * 面试题32： 从上到下打印二叉树 * 思路：用队列保存下一层要打印的结点 * 从队列中出一个结点，打印后将该结点的左右子结点加入队列中，直到队列为空结束 * <p> * 面试题32(题目二)： 从上到下分行打印二叉树 * 思路：在队列中添加分行标志位 * * @param root * @return */ public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> result = new ArrayList<>(); //save result //invalid input if (root == null) return result; LinkedList<TreeNode> queue = new LinkedList<>();//assist queue queue.offer(root); while (!queue.isEmpty()) { TreeNode temp = queue.poll(); result.add(temp.val); if (temp.left != null) queue.offer(temp.left); if (temp.right != null) queue.offer(temp.right); } return result; }
/** * 面试题33：判断数组是否为搜索二叉树的后序遍历序列 * 思路： * 1 数组最后一个元素为该树的根节点 * 2 根据该根节点将数组前面的元素划分为左子树部分和右子树部分 * 3 递归调用，判断是否是后序遍历 * * @param sequence * @return */ public boolean VerifySquenceOfBST(int[] sequence) { //invalid input if (sequence == null) return false; int length = sequence.length; if (length == 0) return false; return VerifySquenceOfBSTCore(sequence, 0, length - 1); } private boolean VerifySquenceOfBSTCore(int[] sequence, int lo, int hi) { if (lo < 0 || hi < 0 || lo >= hi) return true; int rootVal = sequence[hi]; //根结点值 int leftroot = -1; int rightroot = -1; if (sequence[lo] < rootVal) leftroot = lo; int i = -1;//迭代变量 for (i = lo; i < hi; i++) { //找第一个大于根节点的值 if (sequence[i] > rootVal) { rightroot = i; break; } } for (i = i + 1; i < hi; i++) {//判断后面的元素是否均大于根结点值 if (sequence[i] <= rootVal) return false; } return VerifySquenceOfBSTCore(sequence, leftroot, rightroot - 1) && VerifySquenceOfBSTCore(sequence, rightroot, hi - 1); }
/** * 面试题34：二叉树中和为某一值的路径 * 技巧，可以用三层树型结构来代测试 * 思路： * 1 递归的寻找路径，在遍历过程中记录经过的路劲 * 2 递归到叶结点时判断该路径是否符合条件，并添加到结果数组中 * * @param root * @param target * @return */ public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (root == null) return result; ArrayList<Integer> path = new ArrayList<>(); findPath(root, target, path, result); return result; } private void findPath(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) { if (root == null) return; if (root.left == null && root.right == null) { //叶结点 path.add(root.val); if (root.val == target) result.add(new ArrayList<Integer>(path)); path.remove(path.size() - 1); return; } path.add(root.val); findPath(root.left, target - root.val, path, result); findPath(root.right, target - root.val, path, result); path.remove(path.size() - 1); }
/** * 面试题35：复杂链表的复制 * 思路： * 1 在更复杂链表中插入相同的结点 * 2 连接自由结点 * 3 分离两条链表 * * @param pHead * @return */ public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; // * 1 在更复杂链表中插入相同的结点 RandomListNode copyNode = pHead; while (copyNode != null) { RandomListNode node = new RandomListNode(copyNode.label); node.next = copyNode.next; copyNode.next = node; copyNode = copyNode.next.next; } // * 2 连接自由结点 copyNode = pHead; while (copyNode != null) { copyNode.next.random = copyNode.random == null ? null : copyNode.random.next; copyNode = copyNode.next.next; } // * 3 分离两条链表 copyNode = pHead; RandomListNode node = pHead.next; RandomListNode result = pHead.next; while (copyNode.next.next != null) { copyNode.next = copyNode.next.next; node.next = node.next.next; copyNode = copyNode.next; node = node.next; } copyNode.next = null; //容易忽视 return result; }
/** * 面试题36：将二叉搜索树转化成一个排序的双向链表 * 思路 * 1 中序遍历递归地构造双向链表，并返回双向链表的尾部 * * @param pRootOfTree * @return */ private TreeNode tail = null; //链表的尾部 private TreeNode head = null; //链表的头部 public TreeNode Convert(TreeNode pRootOfTree) { ConvertCore(pRootOfTree); return head; } private void ConvertCore(TreeNode node) { if (node == null) return; ConvertCore(node.left); if (tail == null) { tail = node; head = node; } else { tail.right = node; node.left = tail; tail = node; } ConvertCore(node.right); }
/** * 面试题38：打印输入字符串的所有排列 * 递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。 * (1) 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）； * (2) 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。 * 需要注意的几点： * (1) 先确定递归结束的条件； * (2) 去重复； * (3) 按字典顺序排列； * @param str * @return */ public ArrayList<String> Permutation(String str) { char[] strArr = str.toCharArray(); ArrayList<String> result = new ArrayList<>(); if(str==null||str.length()==0) return result; Set<String> res = new TreeSet<>(); //利用TreeSet集合类来实现去重复和排序 Permutation(strArr, 0, res); result.addAll(res); return result; } private void Permutation(char[] strArr, int index, Set<String> result) { if (index == strArr.length) { result.add(new String(strArr)); return; } for (int i = index; i < strArr.length; i++) { exch(strArr, index, i); //确定一个位置的字符 Permutation(strArr, index + 1, result); exch(strArr, index, i); } } private void exch(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }