My Java solution may be unique in the discussion area


  • 0
    L
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> s = new Stack<TreeNode>();
            LinkedList<Integer> list = new LinkedList<Integer>();
            TreeNode p = root;
            TreeNode r = null;
            while(p != null || !s.isEmpty())
            {
            	if(p != null)
            	{
            		s.push(p);
            		p = p.left;
            	}
            	else
            	{
            		p = s.peek();//查看栈顶,但不取出
            		if(p.right != null && p.right != r)
            		{
            			p = p.right;
            			s.push(p);
            			p = p.left;
            		}
            		else
            		{
            			p = s.pop();
            			list.add(p.val);
            			r = p;
            			p = null;
            		}
            	}
            }    
            return list;
        }
    }
    

    tips: I use a variable r to record the most recently visited node.
    Sorry, my English is poor so I don't know how to explain my thoughts in detail. Please read my code and guess my thoughts. :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.