O(n) Java normal in-order traversal.


  • -2
    C

    Normal in-order traversal and looking for better solutions.

    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> rst = new ArrayList<Integer>();
            if(root == null) return rst;
            TreeNode p = root;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            
            while(!stack.empty() || p != null){
                if(p != null){
                    stack.push(p);
                    p = p.left;
                }
                else{
                    TreeNode tmp = stack.pop();
                    rst.add(tmp.val);
                    p = tmp.right;
                }
            }
            return rst;
        }
    }

Log in to reply
 

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