C#: Easy to Understand Solution with Explanation. (Accepted)


  • 0

    0_1522646013640_465cad60-7f5a-4cd1-a2a7-ad03f47ae0e8-image.png
    Basic Idea:

    1. root.val <= p.val: root cannot be p's inorder successor, neither can root's left child. So we only need to consider root's right child.
    2. root.val > p.val: root can be a possible answer, so we store the root node in res. However, we don’t know if there is another node on root's left that is larger than p.val and smaller than res. So we seach in the left subtree.
        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 res = null;
            while (root != null) {
                if (root.val > p.val) {
                    res = root;
                    root = root.left;
                }
                else root = root.right;
            }
            return res;
        }
    }
    

Log in to reply
 

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