L1-二叉树遍历（先，中，后）

Posted on | In |

先序遍历 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
     public void preOrder(TreeNode root,List<Integer> res){
         if(root==null) return;
         res.add(root.val);
         preOrder(root.left,res);
         preOrder(root.right,res);  
     }
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> res = new ArrayList<>();
       preOrder(root, res);
        return res;
    }
    
}

先序遍历 非递归

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class Solution {

	 public static void preorderTraversal(TreeNode root) {
	       Stack<TreeNode> stack=new Stack<TreeNode>();
	     while(!stack.isEmpty()||root!=null)
	       {
	    	   while(root!=null)
	    	   {
	    		   System.out.println(root.val);
	    		   stack.push(root);
	    		   root=root.left;  
	    	   }
	    	   if(!stack.isEmpty())
	    	   {
	    		   root=stack.pop();
	    		   root=root.right;
	    	   }
	    	   
	       }   
	    }
	public static void main(String[] args) {
		TreeNode node=new TreeNode(1);
		node.left=null;
		TreeNode node2=new TreeNode(2);
		node.right=node2;
		TreeNode node3=new TreeNode(3);
		node2.left=node3;
		node2.right=null;
		node3.left=null;
		node3.right=null;
		preorderTraversal(node);
		
	}
}

s.empty()和s==null概念要区分，前者是判断栈空，后者null是表示一个空对象，有没有初始化。

中序遍历 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class Solution {
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
      public void inOrder(TreeNode root,List<Integer> res){
         if(root==null) return;
        
         inOrder(root.left,res);
          res.add(root.val);
        inOrder(root.right,res);  
     }
    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> res = new ArrayList<>();
       inOrder(root, res);
        return res;
	}
}

中序遍历 非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}
public class Solution {
    	public List<Integer> inorderTraversal(TreeNode root) {
		TreeNode node = root;
		List<Integer> l = new ArrayList<Integer>();
		Stack<TreeNode> s = new Stack<TreeNode>();
		while (!s.empty() || node != null) {
			while (node != null) {
				s.push(node);
				//System.out.println(node.val);
				
				node = node.left;
			}
			if (!s.empty()) {
				node = s.pop();
				l.add(node.val);
				node = node.right;
			}

		}
		return l;

	}
}

后序遍历 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
     public void postOrder(TreeNode root,List<Integer> res){
         if(root==null) return;
         postOrder(root.left,res);
         postOrder(root.right,res);
         res.add(root.val);
         
     }
    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> res = new ArrayList<>();
       postOrder(root, res);
        return res;
    }
    
}

e.g. test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package a;

import java.awt.print.Printable;
import java.util.*;

class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}
}

public class Solution {
	 static List<Integer> res = new ArrayList<>();
	 public static void postorderTraversal(TreeNode root) {
	        // write your code here
	        if(root==null) return;
	        postorderTraversal(root.left);
	        postorderTraversal(root.right);
	         res.add(root.val);      
	    }
	public static void main(String[] args) {
		TreeNode node=new TreeNode(1);
		node.left=null;
		TreeNode node2=new TreeNode(2);
		node.right=node2;
		TreeNode node3=new TreeNode(3);
		node2.left=node3;
		node2.right=null;
		node3.left=null;
		node3.right=null;
		postorderTraversal(node);
		if(res==null||res.size()==0) System.out.println("11111"); 
		/*for(Integer it:res)
			System.out.println(it);
	*/
		 for(int    i=0;    i<res.size();    i++)    {   
		      Integer value   =    res.get(i);   
		      System.out.println(value); 
		   }   
	}
}

后序遍历非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package a;

import java.util.*;

public class postOr {
	public static List<Integer> postOrderTraversal(TreeNode root) {
		TreeNode curnode = root;
		TreeNode lastnode = null;
		List<Integer> l = new ArrayList<Integer>();
		Stack<TreeNode> s = new Stack<TreeNode>();
		//把currentNode移到左子树的最下边  
		while (curnode != null) {
				s.push(curnode);
				curnode = curnode.left;
			}
		//进入右子树
			while(!s.empty()) {
				curnode = s.pop();
				// //一个根节点被访问的前提是：无右子树或右子树已被访问过  
				if (curnode.right != null && curnode.right != lastnode) {

					s.push(curnode);
					curnode = curnode.right;
					while (curnode != null) {
						s.push(curnode);
						curnode = curnode.left;
					}
					//走到右子树的最左边
				} else {
					//System.out.println(curnode.val);
					l.add(curnode.val);
					lastnode = curnode;
				}
			}		
		return l;

	}

	public static void main(String[] args) {
		TreeNode node = new TreeNode(1);
		node.left = null;
		TreeNode node2 = new TreeNode(2);
		node.right = node2;
		TreeNode node3 = new TreeNode(3);
		node2.left = node3;
		node2.right = null;
		node3.left = null;
		node3.right = null;
		List<Integer> l = new ArrayList<Integer>();
		l = postOrderTraversal(node);

	}
}

补充:Java中List集合的遍历

一、对List的遍历有三种方式

List list = new ArrayList();
list.add(“testone”);
list.add(“testtwo”);
…

第一种:
for(Iterator it = list.iterator(); it.hasNext(); ) {
….
}
这种方式在循环执行过程中会进行数据锁定, 性能稍差, 同时,如果你想在循环过程中去掉某个元素,只能调用it.remove方法, 不能使用list.remove方法, 否则一定出现并发访问的错误.

第二种:
for(String data : list) {
…..
}
内部调用第一种, 换汤不换药, 因此比Iterator 慢,这种循环方式还有其他限制, 不建议使用它。

第三种:
for(int i=0; i<list.size(); i++) {
A a = list.get(i);
…
}
内部不锁定, 效率最高, 但是当写多线程时要考虑并发操作的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class MapTest {
    private static List<String> list= new ArrayList<String>();
    public static void main(String[]args){
        MapTest  mapTest = new  MapTest();
        mapTest.initList(list);
        mapTest.foreach(list);
        mapTest.forlist(list);
        mapTest.iteratorList(list);
    }
    
    //list 集合中添加10万条数据
    public List initList(List<String> list){
        int i=0;
        int num=6000000;
        for(i=0;i<num;i++){
            list.add("list"+i);
        }
        return list;
    }
    //list 集合遍历 foreach
    
    public void  foreach(List<String> list){
        long start= System.currentTimeMillis();
        for(String data:list){
            String value=data;
        }
        
        long end=System.currentTimeMillis();
        long count=end-start;
        System.out.println("foreach 循环时间"+count);
    }
    // list集合遍历  for
    public void forlist(List<String> list){
        long start=System.currentTimeMillis();
        int i=0;
        for( i=0;i<list.size();i++){
            String value=list.get(i);
        }
        long end=System.currentTimeMillis();
        long count=end-start;
        System.out.println("for list.size() 遍历时间"+count);
    }
    
    // Iterator 遍历循环
    public void iteratorList(List<String> list){
        long start= System.currentTimeMillis();
        for(Iterator<String>  it=list.iterator();it.hasNext();){
            String value=it.next();
        }
        long end=System.currentTimeMillis();
        long count=end-start;
        System.out.println("iterator 遍历时间"+count);
    }

}

测试结果：
（1）、第一次
foreach 遍历时间：55
for list.size()遍历时间：47
iterator 遍历时间：51
（2）、第二次
foreach 遍历时间：54
for list.size()遍历时间：44
iterator 遍历时间：50
（3）、第三次
foreach 遍历时间：48
for list.size()遍历时间：43
iterator 遍历时间：44

补充:static

参考链接1

参考链接2

参考链接3