Clean C# based on Morris Traversal


  • 0
    R
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode InorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode curr = root;
            TreeNode prev = null;
            while(curr != null)
            {
                if(curr.left == null)
                {
                    /* addition to morris traversal */
                    if(prev == p) break;
                    prev = curr;
                    /* end of addition to morris traversal */
                    curr = curr.right;
                }else
                {
                    TreeNode predecessor = curr.left;
                    while(predecessor.right != null && predecessor.right != curr)
                        predecessor = predecessor.right;
                    
                    if(predecessor.right == null)
                    {
                        predecessor.right = curr;
                        curr = curr.left;
                    }else{
                        /* addition to morris traversal */
                        if(prev == p) break;
                        prev = curr;
                        /* end of addition to morris traversal */
                        predecessor.right = null;
                        curr = curr.right;
                    }
                }
            }
            
            return curr;
        }
    }

Log in to reply
 

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