Share my 4 different java solution


  • 0
    C
    // recursive
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        postorderHelper(ret, root);
        return ret;
    }
    private void postorderHelper(List<Integer> list, TreeNode root){
        if(root == null) return;
        postorderHelper(list, root.left);
        postorderHelper(list, root.right);
        list.add(root.val);
    }
    
    // iterator 1 
    public List<Integer> postorderTraversal1(TreeNode root) {
    	List<Integer> ret = new ArrayList<>();
    	if (root == null)
    		return ret;
    	Stack<TreeNode> stack = new Stack<>();
    	TreeNode p = root, lastVisited = null;
    	while(p != null){
    		stack.push(p);
    		p = p.left;
    	}
    	while (!stack.isEmpty()) {
    		p = stack.peek();
    		if(p.right == null || lastVisited == p.right){
    			ret.add(p.val);
    			stack.pop();
    			lastVisited = p;
    		}
    		else{
    			p = p.right;
    			while(p != null){
    				stack.push(p);
    				p = p.left;
    			}
    		}
    	}
    	return ret;
    }
    
    // iterator 2
    public List<Integer> postorderTraversal2(TreeNode root) {
    	List<Integer> ret = new ArrayList<>();
    	if (root == null)
    		return ret;
    	Stack<TreeNode> stack = new Stack<>();
    	TreeNode p = root, lastVisited = null;
    	while (!stack.isEmpty() || p != null) {
    		if(p != null){
    			stack.push(p);
    			p = p.left;
    		}
    		else{
    			TreeNode peek = stack.peek();
    			if(peek.right == null || peek.right == lastVisited){
    				ret.add(peek.val);
    				lastVisited = stack.pop();
    			}
    			else{
    				p = peek.right;
    			}
    		}
    	}
    	return ret;
    }
    
    // morris traversal
    public List<Integer> postorderTraversal3(TreeNode root){
    	List<Integer> ret = new ArrayList<>();
    	if(root == null) return ret;
    	TreeNode dummy = new TreeNode(0);
    	dummy.left = root;
    	TreeNode curNode = dummy;
    	while(curNode != null){
    		if(curNode.left == null){
    			curNode = curNode.right;
    		}
    		else{
    			TreeNode preNode = curNode.left;
    			while(preNode.right != null && preNode.right != curNode){
    				preNode = preNode.right;
    			}
    			if(preNode.right == null){
    				preNode.right = curNode;
    				curNode = curNode.left;
    			}
    			else{
    				reverseVisit(ret, curNode.left, preNode);    				
    				preNode.right = null;
    				curNode = curNode.right;
    			}
    		}
    	}
    	return ret;
    }
    private void reverseVisit(List<Integer> list, TreeNode from, TreeNode to){
    	Stack<TreeNode> stack = new Stack<>();
    	while(from != to){
    		stack.push(from);
    		from = from.right;
    	}
    	stack.push(from);
    	while(!stack.isEmpty()){
    		list.add(stack.pop().val);
    	}
    }

Log in to reply
 

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