The brute force method O(n) time and O(n) space


  • 0
    P

    First, I came out with the most straight forward method like this:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        List<Integer> all;
        public void recoverTree(TreeNode root) {
            List<Integer> list=new ArrayList<>();
            
            inorder(root,list);
            all=new ArrayList<>(list);
            Collections.sort(all);
            List<Integer> find=new ArrayList<>();
            for(int i=0;i<all.size();i++){
                if(list.get(i)!=all.get(i)) find.add(all.get(i));
            }
            int val1=find.get(1);
            int val2=find.get(0);
            change(root,val1,val2);
        }
        void change(TreeNode node,int val1, int val2){
            if(node==null) return;
            if(node.val==val1){
                node.val=val2;
            }else if(node.val==val2){
                node.val=val1;
            }
            change(node.left,val1,val2);
            change(node.right,val1,val2);
        }
        void inorder(TreeNode node, List<Integer> list){
            if(node==null) return;
            inorder(node.left,list);
            list.add(node.val);
            inorder(node.right,list);
            
        }
    }
    

    In order to decrease the space to O(1), I check out the [No Fancy Algorithm, just Simple and Powerful In-Order Traversal]


Log in to reply
 

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