首页 > 编程语言 > 详细

非递归实现先序遍历 java leecode 提交

时间:2014-06-30 11:43:59      阅读:377      评论:0      收藏:0      [点我收藏+]
写完才知道自己学习都是似是而非啊,大家可以也在leecode上提交代码,纯手写,离开eclipse
第一种方式:数据结构书上的,使用栈大概思路。
1.不断将根节点的左孩子的左孩子直到为空,在这个过程入栈。
2.因为栈顶的节点的左孩子为空,所以栈顶的的节点的左子树肯定访问完毕,所以出栈后直接指向右孩子。其实这里面有个思想
迭代和递归的本质相同之处是什么?以后会写一篇我的思考。

public class Solution { public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> arry=new ArrayList<Integer>(); if(root==null) return arry; Stack<TreeNode> s=new Stack<TreeNode>(); TreeNode t=root; while(t!=null||!s.isEmpty()) { while(t!=null) { arry.add(t.val); s.push(t); t=t.left; } if(!s.isEmpty()) { TreeNode tn=s.pop(); t=tn.right; } } return arry; } }

下面这个思路,我用的dfs的非递归方式的思想http://www.cnblogs.com/hansongjiang/p/3812908.html这篇文章说的很清楚

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    	//只能使用非递归方式,来获得List
    	 ArrayList<Integer> arry=new ArrayList<Integer>();
    	Stack<TreeNode> s=new Stack<TreeNode>();
    	s.push(root);
    	while(!s.isEmpty())
    	{
    		
    		TreeNode t=s.pop();
    		arry.add(t.val);
    		
    		if(t.left!=null) s.push(t.left); 
    		if(t.right!=null) s.push(t.right);
    		
    		
    		
    	}
    	return arry;
    		
    	
    	
    	
        
        
        
    }
}

 

非递归实现先序遍历 java leecode 提交,布布扣,bubuko.com

非递归实现先序遍历 java leecode 提交

原文:http://www.cnblogs.com/hansongjiang/p/3813980.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!