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

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

前序遍历：

递归算法：

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

非递归算法：

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

中序遍历

递归算法：

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

非递归算法：

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

后序遍历：

递归算法：

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

非递归算法：

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

哈哈