LeetCode 94、144、145 中序、前序、后序遍历递归算法非递归算法

算法魔功 2018-07-24

在Java中list既可以实现栈,也可以实现队列。后序遍历的非递归算法,是难一点儿。

前序遍历:

递归算法:


  1. public class LC144Try1
  2. {
  3. public List<Integer> preorderTraversal(TreeNode root)
  4. {
  5. List<Integer> arr=new ArrayList<Integer>();
  6. prePass(root,arr);
  7. return arr;
  8. }
  9. public void prePass(TreeNode root,List<Integer> arr){
  10. if(root==null){
  11. return;
  12. }
  13. arr.add(root.val);
  14. prePass(root.left,arr);
  15. prePass(root.right,arr);
  16. }
  17. }

非递归算法:


  1. package test;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. //非递归算法
  5. public class LC144Try2
  6. {
  7. public List<Integer> preorderTraversal(TreeNode root)
  8. {
  9. List<Integer> arr = new ArrayList<Integer>();
  10. List<TreeNode> list= new ArrayList<TreeNode>();
  11. TreeNode p=root;
  12. while(p!=null || list.size()>0){
  13. if(p!=null){
  14. arr.add(p.val);
  15. list.add(p);
  16. p=p.left;
  17. }else{
  18. p=list.remove(list.size()-1);
  19. p=p.right;
  20. }
  21. }
  22. return arr;
  23. }
  24. public static void main(String[] args)
  25. {
  26. LC144Try2 t = new LC144Try2();
  27. TreeNode root= new TreeNode(1);
  28. TreeNode r1= new TreeNode(2);
  29. TreeNode r2= new TreeNode(3);
  30. root.right=r1;
  31. r1.right=r2;
  32. System.out.println(t.preorderTraversal(root));
  33. }
  34. }

中序遍历

递归算法:


  1. package test;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. class TreeNode {
  5. int val;
  6. TreeNode left;
  7. TreeNode right;
  8. TreeNode(int x) { val = x; }
  9. }
  10. //递归
  11. public class LC94Try1
  12. {
  13. public List<Integer> inorderTraversal(TreeNode root) {
  14. List<Integer> arr = new ArrayList<Integer>();
  15. inorderPass(root,arr);
  16. return arr;
  17. }
  18. public void inorderPass(TreeNode root,List<Integer> arr){
  19. if(root==null){
  20. return;
  21. }
  22. inorderPass(root.left,arr);
  23. arr.add(root.val);
  24. inorderPass(root.right,arr);
  25. }
  26. }

非递归算法:


  1. package test;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. //非递归
  5. public class LC94Try2
  6. {
  7. public List<Integer> inorderTraversal(TreeNode root)
  8. {
  9. List<Integer> arr = new ArrayList<Integer>();
  10. List<TreeNode> list = new ArrayList<TreeNode>();
  11. TreeNode p = root;
  12. while (p != null || list.size() > 0)
  13. {
  14. if (p != null)
  15. {
  16. list.add(p);
  17. p = p.left;
  18. }else{
  19. p=list.remove(list.size()-1);
  20. arr.add(p.val);
  21. p=p.right;
  22. }
  23. }
  24. return arr;
  25. }
  26. }

后序遍历:

递归算法:


  1. package test;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. public class LC145Try1
  5. {
  6. public List<Integer> postorderTraversal(TreeNode root)
  7. {
  8. List<Integer> arr = new ArrayList<Integer>();
  9. postorderPass(root,arr);
  10. return arr;
  11. }
  12. public void postorderPass(TreeNode root,List<Integer> arr){
  13. if(root==null){
  14. return;
  15. }else{
  16. postorderPass(root.left,arr);
  17. postorderPass(root.right,arr);
  18. arr.add(root.val);
  19. }
  20. }
  21. }

非递归算法:


  1. package test;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. public class LC145Try2
  5. {
  6. public List<Integer> postorderTraversal(TreeNode root)
  7. {
  8. List<Integer> arr = new ArrayList<Integer>();
  9. List<TreeNode> list = new ArrayList<TreeNode>();
  10. TreeNode p = root;
  11. TreeNode r = root;//上一次读取的位置
  12. while(p!=null || list.size()>0){
  13. if(p!=null){
  14. list.add(p);
  15. p=p.left;
  16. }else{
  17. p=list.get(list.size()-1);
  18. if(p.right!=null && p.right!=r){
  19. p=p.right;
  20. }else{
  21. r=p;
  22. arr.add(p.val);
  23. list.remove(list.size()-1);
  24. p=null;
  25. }
  26. }
  27. }
  28. return arr;
  29. }
  30. }

哈哈

LeetCode 94、144、145 中序、前序、后序遍历递归算法非递归算法

相关推荐