首页 > 试题广场 >

寻找下一个结点

[编程题]寻找下一个结点

热度指数：14366 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定树的根结点指针TreeNode* root和结点的值int p，编写一个函数，寻找该二叉树中指定结点的下一个结点（即中序遍历的后继），并返回p结点的后继结点的值。保证结点的值是小于等于100000的正数且没有重复值，若不存在后继返回-1。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

华科平凡

Python解法如下：

class Successor:
    def findSucc(self, root, p):
        # write code here
        self.arr = []
        self.dfs(root)
        return self.arr[self.arr.index(p) + 1]

    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.arr.append(root.val)
        self.dfs(root.right)

发表于 2017-10-01 20:35:50 回复(2)

Python

Yannyezixin

思路：中序非递归遍历，找到相应那么下一个结点就是结果

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Successor:
    def findSucc(self, root, p):
        if not root:
            return -1
        
        stack = []
        ph = root
        
        isFind = False
        result = -1
        while ph or stack:
            while ph:
                stack.append(ph)
                ph = ph.left
            if stack:
                top = stack.pop()
                if isFind:
                    result = top.val
                    break
                if top.val == p:
                    isFind = True
                
                ph = top.right
        
        return result

发表于 2016-08-03 15:04:30 回复(0)