Three Java 1ms solutions, stack, recursion and morris traversal


  • 1
    S
             //morris traversal    
             public List<Integer> inorderTraversal(TreeNode root) {
                    List<Integer> results = new ArrayList<>();
                    TreeNode crt = root;
                    while (crt != null) {
                        if (crt.left == null) {
                            results.add(crt.val);
                            crt = crt.right;
                        } else {
                            TreeNode temp = crt.left;
                            while (temp.right != null && temp.right != crt) {
                                temp = temp.right;
                            }
                            
                            if (temp.right == null) {
                                temp.right = crt;
                                crt = crt.left;
                            } else {
                                temp.right = null;
                                results.add(crt.val);
                                crt = crt.right;
                            }
                        }
                    }
                    return results;
                }
        
            //using stack
            public List<Integer> inorderTraversal(TreeNode root) {
                    List<Integer> results = new ArrayList<>();
                    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
                    TreeNode crt = root;
                    while (!stack.isEmpty() || crt != null) {
                        if (crt != null) {
                            stack.push(crt);
                            crt = crt.left;
                        } else {
                            crt = stack.pop();
                            results.add(crt.val);
                            crt = crt.right;
                        }
                    }
                return results;
            }
    //recursion
        public List<Integer> inorderTraversal(TreeNode root) {
                List<Integer> results = new ArrayList<>();
                inorderTraversal(root, results);
                return results;
            }
            
            private void inorderTraversal(TreeNode root, List<Integer> results) {
                if (root == null) {
                    return;
                }
                inorderTraversal(root.left, results);
                results.add(root.val);
                inorderTraversal(root.right, results);
            }

Log in to reply
 

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