23题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左向右的顺序打印。

public class Offer23 { public static class BinaryTreeNode{ int value; BinaryTreeNode left; BinaryTreeNode right; } public static void printFromToBottom(BinaryTreeNode root){ // 如果节点为非空 if(root != null){ Queue<BinaryTreeNode> list = new LinkedList<>(); // 根节点入队 list.add(root); // 记录当前处理节点 BinaryTreeNode curNode; // 如果队列非空,则进行处理 while(!list.isEmpty()){ // 删除首节点,即正在处理节点 curNode = list.remove(); // 输出元素值 System.out.print(curNode.value+" "); // 若子节点存在,则入队 if(curNode.left != null){ list.add(curNode.left); } if(curNode.right != null){ list.add(curNode.right); } } } } public static void main(String[] args) { // 8 // / \ // 6 10 // / \ / \ // 5 7 9 11 BinaryTreeNode root = new BinaryTreeNode(); root.value = 8; root.left = new BinaryTreeNode(); root.left.value = 6; root.left.left = new BinaryTreeNode(); root.left.left.value = 5; root.left.right = new BinaryTreeNode(); root.left.right.value = 7; root.right = new BinaryTreeNode(); root.right.value = 10; root.right.left = new BinaryTreeNode(); root.right.left.value = 9; root.right.right = new BinaryTreeNode(); root.right.right.value = 11; printFromToBottom(root); // 1 // / // 3 // / // 5 // / // 7 // / // 9 BinaryTreeNode root2 = new BinaryTreeNode(); root2.value = 1; root2.left = new BinaryTreeNode(); root2.left.value = 3; root2.left.left = new BinaryTreeNode(); root2.left.left.value = 5; root2.left.left.left = new BinaryTreeNode(); root2.left.left.left.value = 7; root2.left.left.left.left = new BinaryTreeNode(); root2.left.left.left.left.value = 9; System.out.println("\n"); printFromToBottom(root2); // 0 // \ // 2 // \ // 4 // \ // 6 // \ // 8 BinaryTreeNode root3 = new BinaryTreeNode(); root3.value = 0; root3.right = new BinaryTreeNode(); root3.right.value = 2; root3.right.right = new BinaryTreeNode(); root3.right.right.value = 4; root3.right.right.right = new BinaryTreeNode(); root3.right.right.right.value = 6; root3.right.right.right.right = new BinaryTreeNode(); root3.right.right.right.right.value = 8; System.out.println("\n"); printFromToBottom(root3); // 1 BinaryTreeNode root4 = new BinaryTreeNode(); root4.value = 1; System.out.println("\n"); printFromToBottom(root4); // null System.out.println("\n"); printFromToBottom(null); } }

24题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

public class Offer24 { /** * 二叉搜索树: * 若左子树不空,则左子树上所有节点值均小于根节点值, * 若右子树不空,则右子树所有节点值均大于根节点值 * */ public static boolean verifySequenceOfBST(int[] sequence){ // 输入验证 if(sequence == null || sequence.length <= 0){ return false; } return verifySequenceOfBST(sequence, 0, sequence.length-1); } /** * 输入一个整数数组,判断是否为二叉搜索树的后序遍历的结果 * @param sequence * @param i * @param j * @return */ private static boolean verifySequenceOfBST(int[] sequence, int start, int end) { // 如果对应要处理的数据只有一个或者没有数据要处理 if(start >= end){ return true; } int index = start; // 找到第一个不小于根节点的元素的位置 while(index < end-1 && sequence[index] < sequence[end]){ index++; } // [start, index-1]为左子树, [index, end-1]为右子树 int right = index; while(index < end-1 && sequence[index] > sequence[end]){ index++; } // 如果符合二叉搜索树,那么index应为end-1 if(index != end-1){ return false; } // 如果以上合法,则递归执行 return verifySequenceOfBST(sequence, start, right-1) && verifySequenceOfBST(sequence, right, end-1); } }

25题目：输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

public class Offer25 { public static class BinaryTreeNode{ int value; BinaryTreeNode left; BinaryTreeNode right; } /** * 输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径 */ public static void findPath(BinaryTreeNode root, int expectedSum){ // 创建一个链表,用于存放根节点到当前处理节点所经过的节点 List<Integer> list = new ArrayList<Integer>(); if(root != null){ findPath(root, 0, expectedSum, list); } } private static void findPath(BinaryTreeNode root, int curSum, int expectedSum, List<Integer> result) { if(root != null){ curSum += root.value; result.add(root.value); if(curSum < expectedSum){ // 递归处理左子树 findPath(root.left, curSum, expectedSum, result); // 递归处理右子树 findPath(root.right, curSum, expectedSum, result); }else if(curSum == expectedSum){ // 当前节点是叶节点,输出结果 if(root.left == null && root.right == null){ System.out.println(result); } } // 移除当前节点 result.remove(result.size()-1); } } }

26题目：请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中，每个结点除了有一个next 域指向下一个结点外，还有一个sibling 指向链表中的任意结点或者null。

public class Offer26 { public static class ComplexListNode{ int value; ComplexListNode next; ComplexListNode sibling; } public static ComplexListNode clone(ComplexListNode head){ if(head == null){ return null; } // 根据我们的思路分为三步: // 1. 复制节点 cloneNodes(head); // 2. 链接sibling字段 connectNodes(head); // 3. 将整个链表拆分,返回复制链表的头结点 return reconnectNodes(head); } /** * 输出链表信息 */ public static void printList(ComplexListNode head){ while(head != null){ System.out.print(head.value + "->"); head = head.next; } System.out.println("null"); } /** * 判断两个链表是否是同一个链表 */ public static boolean isSame(ComplexListNode h1, ComplexListNode h2){ while(h1 != null && h2 != null){ if(h1 == h2){ h1 = h1.next; h2 = h2.next; }else{ return false; } } return h1 == null && h2 == null; } /** * 将刚复制的节点和被复制的节点分离开,还原被复制的链表,同事生成复制链表 * @param head * @return */ private static ComplexListNode reconnectNodes(ComplexListNode head) { if(head == null){ return null; } // 记录复制链表的头结点 ComplexListNode newHead = head.next; // 记录当前处理的复制节点 ComplexListNode pointer = newHead; // 被复制节点的next指向下一个被复制节点 head.next = newHead.next; // 指向新的被复制节点 head = head.next; while(head != null){ // pointer指向复制节点 pointer.next = head.next; pointer = pointer.next; // head的下一个指向复制节点的下一个节点,即原来链表的节点 head.next = pointer.next; // head指向下一个原来链表上的节点 head = pointer.next; } return newHead; } /** * 设置复制节点的sibling字段 * @param head */ private static void connectNodes(ComplexListNode head) { while(head != null){ // 如果当前节点的sibling字段不为空,则进行复制 if(head.sibling != null){ // 此时head.sibling表示被复制的节点的sibling所指向的节点 // 那么它的下一个节点就是我们要找的节点 head.next.sibling = head.sibling.next; } head = head.next.next; } } /** * 复制一个链表,将复制后的节点插入到被复制的节点后面,只连接复制节点的next字段 * @param head */ private static void cloneNodes(ComplexListNode head) { while(head != null){ // 创建一个新的节点 ComplexListNode tmp = new ComplexListNode(); tmp.value = head.value; tmp.next = head.next; head.next = tmp; // 指向下一个要进行复制的节点 head = tmp.next; } } }