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

  • Z时代
  • 2024-01-10
  • 分类：综合

python

寻找下一个结点 牛客网 程序员面试金典 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

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

以上是 寻找下一个结点 牛客网 程序员面试金典 C++ java Python 的全部内容， 来源链接： utcz.com/z/388973.html

回到顶部