剑指offer 面试8题

面试8题：

题目：二叉树的下一个节点

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

解题思路：详见剑指offer P65页

解题代码：

# -*- coding:utf-8 -*-

# class TreeLinkNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

#         self.next = None

class Solution:

    def GetNext(self, pNode):

        # write code here

        if not pNode:

            return

        #如果该节点有右子树，那么下一个节点就是它右子树中的最左节点

        elif pNode.right!=None:

            pNode=pNode.right

            while pNode.left!=None:

                pNode=pNode.left

            return pNode

        #如果一个节点没有右子树，，并且它还是它父节点的右子节点

        elif pNode.next!=None and pNode.next.right==pNode:

            while pNode.next!=None and pNode.next.left!=pNode:

                pNode=pNode.next

            return pNode.next

        #如果一个节点是它父节点的左子节点，那么直接返回它的父节点

        else:

            return pNode.next

巴特西

剑指offer 面试8题

最新文章

热门文章