现在的位置: 首页 > 综合 > 正文

leetcode_94_Binary Tree Inorder Traversal

2019年06月02日 ⁄ 综合 ⁄ 共 766字 ⁄ 字号 评论关闭

1.描述

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

2.思路

a.先遍历左子树直至左孩子为空

b.然后看当前节点的右子树是否为空,为空,则访问当前节点,弹出当前节点,重新判断;不为空,访问当前节点,然后将当前节点弹出,并将当前节点的右孩子进栈,返回a

c.这中间需要注意的是,在弹出当前节点后,在获得栈顶的当前节点前先判断下栈是否为空

3.代码

public List<Integer> inorderTraversal(TreeNode root) {
	     List<Integer>list=new ArrayList<Integer>();
	     if(root==null)
			 return list;
	     Stack<TreeNode>st=new Stack<TreeNode>();
	     st.push(root);
	     TreeNode top=null;
	     while(!st.empty())
	     {
	    	 top=st.peek();
	    	 while(top.left!=null)
	    	 {
	    		 st.push(top.left);
	    		 top=top.left;
	    	 }
	    	 while(top.right==null)
	    	 {
	    		 list.add(top.val);
	    		 st.pop();
	    		 if(!st.empty())
	    			 top=st.peek();
	    		 else
	    			 break;
	    	 }
	    	 if(!st.empty())
	    	 {
	    		 list.add(top.val);
		    	 st.pop();
		    	 st.push(top.right);
	    	 }
	    	 
	     }
	     return list;
	 }

4.结果

抱歉!评论已关闭.