二叉树的前序遍历：
二叉树的前序遍历的记忆法则是“根左右"，即先遍历根节点，再遍历左子树节点，再遍历右子树节点。
如图所示：
其遍历结果为【A, B, D, E, C, F, G】
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
数据范围：二叉树的节点数量满足1≤n≤100 ，二叉树节点的值满足1≤val≤100，树的各节点的值各不相同
示例 1：
1. 输入： 2. {1,#,2,3} 3. 返回值： 4. [1,2,3]
一、解题思路：递归
1. public class Solution { 2. 3. List<Integer> list = new ArrayList<>(); 4. 5. public int[] preorderTraversal (TreeNode root) { 6. List<Integer> list = preOrder(root); 7. int[] res = new int[list.size()]; 8. for (int i = 0; i < list.size(); i++) { 9. res[i] = list.get(i); 10. } 11. return res; 12. } 13. 14. List<Integer> preOrder(TreeNode node) { 15. if (node == null) { 16. return list; 17. } 18. list.add(node.val); 19. preOrder(node.left); 20. preOrder(node.right); 21. return list; 22. } 23. }
二、解题思路：迭代
1. import java.util.*; 2. 3. /* 4. * public class TreeNode { 5. * int val = 0; 6. * TreeNode left = null; 7. * TreeNode right = null; 8. * public TreeNode(int val) { 9. * this.val = val; 10. * } 11. * } 12. */ 13. 14. public class Solution { 15. /** 16. * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 17. * 18. * 19. * @param root TreeNode类 20. * @return int整型一维数组 21. */ 22. public int[] preorderTraversal (TreeNode root) { 23. // 结果集合 24. ArrayList<Integer> arr = new ArrayList(); 25. if(root == null) { 26. return new int[0]; 27. } 28. TreeNode current; 29. // LinkedList 当作栈来使用 30. LinkedList<TreeNode> list = new LinkedList<TreeNode>(); 31. list.addFirst(root); 32. while(!list.isEmpty()) { 33. current = list.removeFirst(); 34. arr.add(current.val); 35. if(current.right != null) { 36. list.addFirst(current.right); 37. } 38. if(current.left != null) { 39. list.addFirst(current.left); 40. } 41. } 42. // 循环赋值。 43. int[] res = new int[arr.size()]; 44. for(int i = 0; i < arr.size(); i++) { 45. res[i] = arr.get(i); 46. } 47. return res; 48. } 49. }
二叉树的中序遍历 ：
中序遍历是 二叉树遍历 的一种，也叫做 中根遍历 、中序周游。 在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
给定一个二叉树的根节点root，返回它的中序遍历结果。
数据范围：树上节点数满足10000≤n≤1000，树上每个节点的值满足 −1000≤val≤1000
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1：
1. 输入： 2. {1,2,#,#,3} 3. 返回值： 4. [2,3,1]
一、解题思路：递归
1. import java.util.*; 2. public class Solution { 3. public void inorder(List<Integer> list, TreeNode root){ 4. //遇到空节点则返回 5. if(root == null) 6. return; 7. //先去左子树 8. inorder(list, root.left); 9. //再访问根节点 10. list.add(root.val); 11. //最后去右子树 12. inorder(list, root.right); 13. } 14. 15. public int[] inorderTraversal (TreeNode root) { 16. //添加遍历结果的数组 17. List<Integer> list = new ArrayList(); 18. //递归中序遍历 19. inorder(list, root); 20. //返回的结果 21. int[] res = new int[list.size()]; 22. for(int i = 0; i < list.size(); i++) 23. res[i] = list.get(i); 24. return res; 25. } 26. }
二、解题思路：迭代
1. import java.util.*; 2. public class Solution { 3. public int[] inorderTraversal (TreeNode root) { 4. //添加遍历结果的数组 5. List<Integer> list = new ArrayList(); 6. Stack<TreeNode> s = new Stack<TreeNode>(); 7. //空树返回空数组 8. if(root == null) 9. return new int[0]; 10. //当树节点不为空或栈中有节点时 11. while(root != null || !s.isEmpty()){ 12. //每次找到最左节点 13. while(root != null){ 14. s.push(root); 15. root = root.left; 16. } 17. //访问该节点 18. TreeNode node = s.pop(); 19. list.add(node.val); 20. //进入右节点 21. root = node.right; 22. } 23. //返回的结果 24. int[] res = new int[list.size()]; 25. for(int i = 0; i < list.size(); i++) 26. res[i] = list.get(i); 27. return res; 28. } 29. }
二叉树的后序遍历 ：
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点
给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围：二叉树的节点数量满足 1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同
1. 输入： 2. {1,#,2,3} 3. 返回值： 4. [3,2,1]
一、解题思路：递归
1. import java.util.*; 2. public class Solution { 3. public void postorder(List<Integer> list, TreeNode root){ 4. //遇到空节点则返回 5. if(root == null) 6. return; 7. //先去左子树 8. postorder(list, root.left); 9. //再去右子树 10. postorder(list, root.right); 11. //最后访问根节点 12. list.add(root.val); 13. } 14. 15. public int[] postorderTraversal (TreeNode root) { 16. //添加遍历结果的数组 17. List<Integer> list = new ArrayList(); 18. //递归后序遍历 19. postorder(list, root); 20. //返回的结果 21. int[] res = new int[list.size()]; 22. for(int i = 0; i < list.size(); i++) 23. res[i] = list.get(i); 24. return res; 25. } 26. }
二、解题思路：迭代
1. import java.util.*; 2. public class Solution { 3. public int[] postorderTraversal (TreeNode root) { 4. //添加遍历结果的数组 5. List<Integer> list = new ArrayList(); 6. Stack<TreeNode> s = new Stack<TreeNode>(); 7. TreeNode pre = null; 8. while(root != null || !s.isEmpty()){ 9. //每次先找到最左边的节点 10. while(root != null){ 11. s.push(root); 12. root = root.left; 13. } 14. //弹出栈顶 15. TreeNode node = s.pop(); 16. //如果该元素的右边没有或是已经访问过 17. if(node.right == null || node.right == pre){ 18. //访问中间的节点 19. list.add(node.val); 20. //且记录为访问过了 21. pre = node; 22. }else{ 23. //该节点入栈 24. s.push(node); 25. //先访问右边 26. root = node.right; 27. } 28. } 29. //返回的结果 30. int[] res = new int[list.size()]; 31. for(int i = 0; i < list.size(); i++) 32. res[i] = list.get(i); 33. return res; 34. } 35. }
