1. 树的前序遍历可以用栈来实现。方法如下：
（1）先访问当前节点的值。
（2）访问当前节点的右节点，如果不为空，将其压入栈中。
（3）访问当前节点的左节点，如果不为空，将其压入栈中。
（4）迭代实现。
1 //前序遍历的顺序节点存放在list中 2 public List<TreeNode> preorderUsingStack(TreeNode root) { 3 List<TreeNode> list = new LinkedList<TreeNode>(); 4 if (root == null) { 5 return list; 6 } 7 Stack<TreeNode> stack = new Stack<TreeNode>(); 8 stack.push(root); 9 while (!stack.isEmpty()) { 10 TreeNode tempNode = stack.pop(); 11 //先存入当前节点 12 list.add(tempNode); 13 //注意是先压栈右子节点再压栈左子节点 14 if (tempNode.right != null) { 15 stack.push(tempNode.right); 16 } 17 if (tempNode.left != null) { 18 stack.push(tempNode.left); 19 } 20 } 21 return list; 22 }
注：前序遍历、中序遍历、后序遍历都有traversal、divided conquer、no-recursion三种方法来做。其中后序遍历的no-recursion算法要复杂些。
中序遍历
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree [1,null,2,3], 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively?
递归：
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> inorderTraversal(TreeNode root) { 12 List<Integer> result = new ArrayList<>(); 13 if (root == null) { 14 return result; 15 } 16 inorder(root, result); 17 return result; 18 } 19 public void inorder(TreeNode root, List<Integer> result) { 20 if (root == null) { 21 return; 22 } 23 inorder(root.left, result); 24 result.add(root.val); 25 inorder(root.right, result); 26 } 27 }
迭代：
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> inorderTraversal(TreeNode root) { 12 List<Integer> result = new ArrayList<>(); 13 if (root == null) { 14 return result; 15 } 16 Stack<TreeNode> stack = new Stack<>(); 17 TreeNode cur = root; 18 while (cur != null || !stack.isEmpty()) { 19 while (cur != null) { 20 stack.push(cur); 21 cur = cur.left; 22 } 23 cur = stack.pop(); 24 result.add(cur.val); 25 cur = cur.right; 26 } 27 return result; 28 } 29 }
后序遍历
recursion
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> postorderTraversal(TreeNode root) { 12 List<Integer> result = new ArrayList<>(); 13 if (root == null) { 14 return result; 15 } 16 dfsHelper(root, result); 17 return result; 18 } 19 public void dfsHelper(TreeNode root, List<Integer> result) { 20 if (root == null) { 21 return; 22 } 23 dfsHelper(root.left, result); 24 dfsHelper(root.right, result); 25 result.add(root.val); 26 } 27 }
iterator
设置pre和cur指针，它们之间有6中位置关系，根据位置关系选择不同的操作。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> postorderTraversal(TreeNode root) { 12 List<Integer> result = new ArrayList<>(); 13 if (root == null) { 14 return result; 15 } 16 TreeNode pre = null; 17 TreeNode cur = root; 18 Stack<TreeNode> stack = new Stack<>(); 19 stack.push(root); 20 while (!stack.isEmpty()) { 21 cur = stack.peek(); 22 if (pre == null || pre.left == cur || pre.right == cur) { 23 if (cur.left != null) { 24 stack.push(cur.left); 25 } else if (cur.right != null) { 26 stack.push(cur.right); 27 } 28 } else if (cur.left == pre) { 29 if (cur.right != null) { 30 stack.push(cur.right); 31 } 32 } else { 33 result.add(cur.val); 34 stack.pop(); 35 } 36 pre = cur; 37 } 38 return result; 39 } 40 }
3. 常见排序算法
（1）快速排序模版
1 public class Solution { 2 /** 3 * @param A an integer array 4 * @return void 5 */ 6 public void sortIntegers2(int[] A) { 7 // Write your code here 8 if (A == null || A.length == 0) { 9 return; 10 } 11 quickSort(A, 0, A.length - 1); 12 } 13 private void quickSort(int[] A, int start, int end) { 14 //注意是>=,不能只是==，>说明没有元素可以排，=说明只有一个元素可排，不需要排直接返回即可。 15 if (start >= end) { 16 return; 17 } 18 int pivot = A[(start + end) / 2]; 19 int left = start; 20 int right = end; 21 while (left <= right) { 22 while (left <= right && A[left] < pivot) { 23 left++; 24 } 25 while (left <= right && A[right] > pivot) { 26 right--; 27 } 28 if (left <= right) { 29 int temp = A[left]; 30 A[left] = A[right]; 31 A[right] = temp; 32 left++; 33 right--; 34 } 35 } 36 quickSort(A, start, right); 37 quickSort(A, left, end); 38 } 39 }
（2）归并排序模版
1 public class Solution { 2 /** 3 * @param A an integer array 4 * @return void 5 */ 6 public void sortIntegers2(int[] A) { 7 // Write your code here 8 if (A == null || A.length == 0) { 9 return; 10 } 11 int[] temp = new int[A.length]; 12 mergeSort(A, 0, A.length - 1, temp); 13 } 14 private void mergeSort(int[] A, int start, int end, int[] temp) { 15 if (start >= end) { 16 return; 17 } 18 mergeSort(A, start, (start + end) / 2, temp); 19 mergeSort(A, (start + end) / 2 + 1, end, temp); 20 merge(A, start, end, temp); 21 } 22 private void merge(int[] A, int start, int end, int[] temp) { 23 int mid = (start + end) / 2; 24 int leftIndex = start; 25 int rightIndex = mid + 1; 26 int index = leftIndex; 27 while (leftIndex <= mid && rightIndex <= end) { 28 if (A[leftIndex] < A[rightIndex]) { 29 temp[index++] = A[leftIndex++]; 30 } else { 31 temp[index++] = A[rightIndex++]; 32 } 33 } 34 while (leftIndex <= mid) { 35 temp[index++] = A[leftIndex++]; 36 } 37 while (rightIndex <= end) { 38 temp[index++] = A[rightIndex++]; 39 } 40 //注意复制是先A的start - end复制到temp中的start - end，然后temp中的start - end复制到A中的start - end 41 for (int i = start; i <= end; i++) { 42 A[i] = temp[i]; 43 } 44 } 45 }