Python二叉树的下一个结点

本文阅读 3 分钟
首页 Python笔记 正文

三种情况:当前节点有右子树的话,当前节点的下一个结点是右子树中的最左子节点;当前节点无右子树但是是父节点的左子节点,下一个节点是当前结点的父节点;当前节点无右子树而且是父节点的右子节点,则一直向上遍历,直到找到最靠近的一个祖先节点pNode,pNode是其父节点的左子节点,那么输入节点的下一个结点就是pNode的父节点。

  1. '''
  2. 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
  3. 注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
  4. '''
  5. # -*- coding:utf-8 -*-
  6. class TreeLinkNode:
  7. def __init__(self, x):
  8. self.val = x
  9. self.left = None
  10. self.right = None
  11. self.next = None
  12. class Solution:
  13. def GetNext(self, pNode):
  14. if pNode == None:
  15. return
  16. pNext = None
  17. if pNode.right != None:
  18. pRight = pNode.right
  19. while pRight.left != None:
  20. pRight = pRight.left
  21. pNext= pRight
  22. elif pNode.next != None:
  23. pCurrent = pNode
  24. pParent = pCurrent.next
  25. while pParent != None and pCurrent == pParent.right:
  26. pCurrent = pParent
  27. pParent = pCurrent.next
  28. pNext = pParent
  29. return pNext
  30. class Solution2:
  31. def GetNext(self, pNode):
  32. # 输入是一个空节点
  33. if pNode == None:
  34. return None
  35. # 注意当前节点是根节点的情况。所以在最开始设定pNext = None, 如果下列情况都不满足, 说明当前结点为根节点, 直接输出None
  36. pNext = None
  37. # 如果输入节点有右子树,则下一个结点是当前节点右子树中最左节点
  38. if pNode.right:
  39. pNode = pNode.right
  40. while pNode.left:
  41. pNode = pNode.left
  42. pNext = pNode
  43. else:
  44. # 如果当前节点有父节点且当前节点是父节点的左子节点, 下一个结点即为父节点
  45. if pNode.next and pNode.next.left == pNode:
  46. pNext = pNode.next
  47. # 如果当前节点有父节点且当前节点是父节点的右子节点, 那么向上遍历
  48. # 当遍历到当前节点为父节点的左子节点时, 输入节点的下一个结点为当前节点的父节点
  49. elif pNode.next and pNode.next.right == pNode:
  50. pNode = pNode.next
  51. while pNode.next and pNode.next.right == pNode:
  52. pNode = pNode.next
  53. # 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点
  54. # 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点
  55. if pNode.next:
  56. pNext = pNode.next
  57. return pNext
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python删除链表中重复的结点
« 上一篇 01-21
Python对称的二叉树
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18497 篇
  • 评论总数:
    53318 条
  • 标签总数:
    8873 个
  • 总浏览量:
    22671943 次
  • 最后更新:
    3月27日

最多点赞

随便看看

标签TAG