网站首页菜单栏模块怎么做的/it培训机构培训费用

题目描述

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

思路及Python实现

• 理一下题目，画出大致示意1；再看要求的中序遍历的下一个结点，如下图2，观察中序遍历的输出顺序！
  
  
• 如果pNode是一个左结点，那么它的下一个结点永远是它的父结点，所以要利用这一特性；如果pNode是位于一个“父结点”上，那么它的下一个结点会有两种情况：一是，如果右结点存在，那么下一个结点就是，不断去找到它的左子树的最后一层左结点（如果多没有，最上一层就是当前存在的右节点）；如果右结点不存在，那么下一个结点就是当前父结点的上一个位于左子树的父结点，一定是是不断向上找左侧的，如果只有一层，那就只能是只存在根结点root，那么它不存在下一个！
• 所以具体做法是：先判断给出的pNode存在右结点的情况，然后处理它不存在的情况

class TreeLinkNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneself.next = Noneclass Solution:def GetNext(self, pNode):if pNode.right:temp_node = pNode.rightwhile temp_node.left:temp_node = temp_node.leftreturn temp_nodeelse:temp_node = pNodewhile temp_node.next: # 通过指针找到它的父结点if temp_node.next.left == temp_node: # 如果父结点的左侧就是给的结点，直接返回return temp_node.nexttemp_node = temp_node.next # 如果没有找到位于左侧的父结点，就一直找return None # 只有一个根root的情况