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

# 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

 

转载于:https://www.cnblogs.com/vercont/p/10210324.html

相关资源：JAVA上百实例源码以及开源项目