18ms Java solution, with in-order traversal and sorting, O(nlogn) time and O(n) space


  • 3
    Y
    public class Solution {
        public void recoverTree(TreeNode root) {
            // in-order traversal of treenodes, followed by sorting and reassignment of values
            List<TreeNode> inorder = inorder(root);
            List<Integer> inorderNumbers = new ArrayList<Integer>();
            for (TreeNode node : inorder) {
                inorderNumbers.add(node.val);
            }
            inorderNumbers.sort(null);
            for (int i = 0; i < inorder.size(); i++) {
                inorder.get(i).val = inorderNumbers.get(i);
            }
        }
        
        private List<TreeNode> inorder (TreeNode root) {
            List<TreeNode> result = new ArrayList<TreeNode>();
            if (root == null) {
                return result;
            }
            result.addAll(inorder(root.left));
            result.add(root);
            result.addAll(inorder(root.right));
            return result;
        }
    }

  • 2

    I like this kind of easy solution


Log in to reply
 

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