1 Star 0 Fork 1.5K

沐瑶 / LearningNotes

forked from 陌溪 / LearningNotes 
Create your Gitee Account
Explore and code with more than 6 million developers,Free private repositories !:)
Sign up
Clone or download
README.md 1.37 KB
Copy Edit Web IDE Raw Blame History
陌溪 authored 2020-06-28 15:46 . 增加算法部分

二叉树的下一个节点

来源

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

步骤

  • 寻找右子树,如果存在就一直找右子树的最左边就是下一个节点
  • 没有右子树,就寻找它的父节点,一直找到它是父节点的左子树,打印父节点

image-20200616211510448

代码

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def GetNext(self, pNode):
        # 1.寻找右子树,如果存在就一直找到右子树的最左边,就是下一个节点
        # 2.没有右子树,就寻找他的父节点,一直找到它是父节点的左子树,打印父节点
        if pNode.right:
            tmpNode = pNode.right
            while tmpNode.left:
                tmpNode = tmpNode.left
            return tmpNode
        else:
            tmpNode = pNode
            while tmpNode.next:
                if tmpNode.next.left == tmpNode:
                    return tmpNode.next
                tmpNode = tmpNode.next
            return None

Comment ( 0 )

Sign in for post a comment

1
https://gitee.com/muyao_vip/LearningNotes.git
git@gitee.com:muyao_vip/LearningNotes.git
muyao_vip
LearningNotes
LearningNotes
master

Search

102255 3a0e046c 1850385 102255 7aaa926c 1850385