Has been a long time since wrote Morris, just for practice


  • 0
    class Solution {
        TreeNode bigNode = null, smallNode = null, prev = null;
    
        public void recoverTree(TreeNode root) {
            if (root == null) return;
            // Morris Starts Here
            TreeNode node = root;
            while (node != null) {
                if (node.left == null) {
                    checkNode(node);
                    node = node.right;          
                } else {
                    TreeNode r = node.left;
                    while (r.right != null && r.right != node) r = r.right;
                    if (r.right == null) {
                        r.right = node;
                        node = node.left;
                    } else {
                        r.right = null;
                        checkNode(node);
                        node = node.right;
                    }
                }
            }
            swapValue(bigNode, smallNode);
        }
        
        private void swapValue(TreeNode t1, TreeNode t2) {
            int tmp = t1.val;
            t1.val = t2.val;
            t2.val = tmp;
        }
        
        private void checkNode(TreeNode node) {
            if (prev != null) {
                if (prev.val > node.val) {
                    bigNode = bigNode == null ? prev : bigNode;
                    smallNode = node;
                }
            }
            prev = node;
        }
    }
    

Log in to reply
 

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