python3 解法, 执行用时: 72 ms, 内存消耗: 20.4 MB, 提交时间: 2023-10-21 23:35:18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        successor = None
        if p.right:
            successor = p.right
            while successor.left:
                successor = successor.left
            return successor
        node = root
        while node:
            if node.val > p.val:
                successor = node
                node = node.left
            else:
                node = node.right
        return successor

javascript 解法, 执行用时: 80 ms, 内存消耗: 50.8 MB, 提交时间: 2023-10-21 23:34:31

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @return {TreeNode}
 */
var inorderSuccessor = function(root, p) {
    let successor = null;
    if (p.right) {
        successor = p.right;
        while (successor.left) {
            successor = successor.left;
        }
        return successor;
    }
    let node = root;
    while (node) {
        if (node.val > p.val) {
            successor = node;
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return successor;
};

var inorderSuccessor2 = function(root, p) {
    const stack = [];
    let prev = null, curr = root;
    while (stack.length || curr) {
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        if (prev === p) {
            return curr;
        }
        prev = curr;
        curr = curr.right;
    }
    return null;
};

golang 解法, 执行用时: 12 ms, 内存消耗: 6.7 MB, 提交时间: 2023-10-21 23:34:04

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    st := []*TreeNode{}
    var pre, cur *TreeNode = nil, root
    for len(st) > 0 || cur != nil {
        for cur != nil {
            st = append(st, cur)
            cur = cur.Left
        }
        cur = st[len(st)-1]
        st = st[:len(st)-1]
        if pre == p {
            return cur
        }
        pre = cur
        cur = cur.Right
    }
    return nil
}


func inorderSuccessor2(root *TreeNode, p *TreeNode) *TreeNode {
    var successor *TreeNode
    if p.Right != nil {
        successor = p.Right
        for successor.Left != nil {
            successor = successor.Left
        }
        return successor
    }
    node := root
    for node != nil {
        if node.Val > p.Val {
            successor = node
            node = node.Left
        } else {
            node = node.Right
        }
    }
    return successor
}

python3 解法, 执行用时: 80 ms, 内存消耗: 20.3 MB, 提交时间: 2023-10-21 23:33:26

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        st, pre, cur = [], None, root
        while st or cur:
            while cur:
                st.append(cur)
                cur = cur.left
            cur = st.pop()
            if pre == p:
                return cur
            pre = cur
            cur = cur.right
        return None

java 解法, 执行用时: 2 ms, 内存消耗: 43 MB, 提交时间: 2023-10-21 23:32:51

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 递归实现
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(p==null||root==null){
            return null;
        }
        if(root.val<=p.val){//当前和左边都不可能>p
            return inorderSuccessor(root.right,p);
        }
        //root>p
        TreeNode res1=inorderSuccessor(root.left,p);
        if(res1!=null&&res1.val<root.val){
            return res1;
        }else{
            return root;
        }
    }
    
    // 迭代
    public TreeNode inorderSuccessor1(TreeNode root, TreeNode p) {
        if(p==null||root==null){
            return null;
        }
        TreeNode cur=root;
        TreeNode res=null;
        while(cur!=null){
            if(cur.val<=p.val){
                cur=cur.right;
            }else{
                if(res==null||res.val>cur.val){
                    res=cur;
                }
                cur=cur.left;
            }
        }
        return res;
    }
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 22.5 MB, 提交时间: 2023-10-21 23:31:42

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* res = NULL;
        while (root) {
            if (p->val < root->val) {
                res = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return res;
    }
};