寻找下一个结点 牛客网 程序员面试金典 C++ java Python

• 题目描述
• 请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
• 给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。

C++

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};*/

class Successor {

    //run:5ms memory:504k

    TreeNode* pre = new TreeNode(-1);

public:

    int findSucc(TreeNode* root, int p){

        if (NULL == root) return -1;

        int ret = findSucc(root->left,p);

        if (-1 == ret){

            if (pre->val == p) return root->val;

            pre = root;

            return findSucc(root->right,p);

        }

        return ret;

    }

};

java

import java.util.*;

/*

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}*/

public class Successor {

    //run:32ms memory:10444k

    private TreeNode pre = new TreeNode(-1);

    public int findSucc(TreeNode root, int p) {

        if (root == null) return -1;

        int ret = findSucc(root.left, p);

        if (ret == -1) {

            if (pre.val == p) return root.val;

            pre = root;

            return findSucc(root.right, p);

        }

        return ret;

    }

}

Python

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Successor:

    #run:43ms memory:5856k

    def __init__(self):

        self.pre = TreeNode(-1)

    def findSucc(self, root, p):

        if None == root: return -1

        ret = self.findSucc(root.left,p)

        if -1 == ret:

            if self.pre.val == p: return root.val

            self.pre = root

            return self.findSucc(root.right,p)

        return ret