3 different ways to do post order traversal (ALL iterative and O(N))


  • 0
    B

    State & Call Stack mimic

        public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> ret = new ArrayList<>();
          if(root == null) return ret;
    
          Stack<State> stack = new Stack<>();
          stack.push(new State(root, false, false));
    
          while(!stack.isEmpty()) {
            State state = stack.pop();
            TreeNode node = state.node;
            if(node == null) continue;
            if(state.completedRight) {
              ret.add(node.val);
            } else if(state.completedLeft) {
              stack.push(new State(node, true, true));
              stack.push(new State(node.right, false, false));
            } else {
              stack.push(new State(node, true, false));
              stack.push(new State(node.left, false, false));
            }
          }
    
          return ret;
        }
    
        private static class State {
          final TreeNode node;
          final boolean completedLeft;
          final boolean completedRight;
    
          State(TreeNode node, boolean completedLeft, boolean completedRight) {
            this.node = node;
            this.completedLeft = completedLeft;
            this.completedRight = completedRight;
          }
        }
    

    Double stack (second stack to record right direction travelling)

        public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> ret = new ArrayList<>();
    
          Stack<TreeNode> stack = new Stack<>();
          Stack<TreeNode> rights = new Stack<>();
          pushAllLefts(root, stack);
    
          while(!stack.isEmpty()) {
            TreeNode next = stack.peek();
            if(!rights.isEmpty() && rights.peek() == next) {
              stack.pop();
              rights.pop();
              ret.add(next.val);
            } else {
              rights.push(next);
              pushAllLefts(next.right, stack);
            }
          }
    
          return ret;
        }
    
        private static void pushAllLefts(TreeNode node, Stack<TreeNode> stack) {
          while(node != null) {
            stack.push(node);
            node = node.left;
          }
        }
    

    Morris: right -> left -> current. and reverse order

        public List<Integer> postorderTraversal(TreeNode root) {
          LinkedList<Integer> ret = new LinkedList<>();
          Stack<TreeNode> stack = new Stack<>();
          if(root == null) return ret;
    
          stack.push(root);
          while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            ret.addFirst(cur.val);
            if(cur.left != null) stack.push(cur.left);
            if(cur.right != null) stack.push(cur.right);
          }
          return ret;
        }
    

Log in to reply
 

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