[关闭]
@liweiwei1419 2019-02-10T15:23:41.000000Z 字数 965 阅读 953

LeetCode 第 94 题:中序遍历二叉树



传送门:二叉树的中序遍历

给定一个二叉树,返回它的中序 遍历。

示例:

  1. 输入: [1,null,2,3]
  2. 1
  3. \
  4. 2
  5. /
  6. 3
  7. 输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

分析:左结点一直入栈,然后出栈的时候,当前结点有右边结点的就变成右边结点。

image-20190120184638930

解法1:教科书上的写法

Python 代码:

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.left = None
  6. # self.right = None
  7. class Solution(object):
  8. def inorderTraversal(self, root):
  9. """
  10. :type root: TreeNode
  11. :rtype: List[int]
  12. """
  13. res = []
  14. stack = []
  15. node = root
  16. while node or stack:
  17. while node:
  18. stack.append(node)
  19. node = node.left
  20. node = stack.pop()
  21. res.append(node.val)
  22. node = node.right
  23. return res

解法2:万能解法

之所以称之为“万能”,是因为只要改变入栈的顺序,这个模板可以完成“前序遍历”和“中序遍历”。

Python 代码:

  1. class TreeNode:
  2. def __init__(self, x):
  3. self.val = x
  4. self.left = None
  5. self.right = None
  6. class Solution:
  7. def inorderTraversal(self, root):
  8. if not root:
  9. return []
  10. stack = [(1, root)]
  11. res = []
  12. while stack:
  13. command, node = stack.pop()
  14. if command == 0:
  15. res.append(node.val)
  16. else:
  17. if node.right:
  18. stack.append((1, node.right))
  19. stack.append((0, node))
  20. if node.left:
  21. stack.append((1, node.left))
  22. return res

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注