二叉树的中序遍历
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的中序遍历,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2041字,纯文字阅读大概需要3分钟。
内容图文
![二叉树的中序遍历](/upload/InfoBanner/zyjiaocheng/1257/f08b7eb27ed94804960bd6803480e1d1.jpg)
题目:给定一个二叉树,返回它的中序 遍历。
来源:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
法一:网上的代码
思路:利用栈的递归,对每次取的节点进行标记,第一次遍历该节点时,标记为灰色,左子树和右子树标记为白色,注意入栈的顺序是右 中 左,因为最后存储的顺序的左 中 右.
![技术分享图片](/img/jia.gif)
![技术分享图片](/img/jian.gif)
#
Definition for a binary tree node.
class
TreeNode:
def
__init__
(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode):
print(‘root is:‘)
print(root)
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
# 如果节点为空则结束本次循环,继续从栈从取元素if node is None: continueif color == WHITE:
# 注意这里为了实现中序遍历,入栈的顺序是右 中 左 stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
# 如果不为白色,说明已经被遍历过了,则放入res中else:
res.append(node.val)
return res
# 将list转化为二叉树
# 这里是用队列实现了一个层序遍历,即将list从左往右一层一层依次填充二叉树def stringToTreeNode(input):
input = input.strip()
input = input[1:-1]
ifnot input:
return None
inputValues = [s.strip() for s in input.split(‘,‘)]
root = TreeNode(int(inputValues[0]))
nodeQueue = [root]
front = 0
index = 1
while index < len(inputValues):
node = nodeQueue[front]
# front指向的是队列的头,即出队列的
front = front + 1
item = inputValues[index]
index = index + 1
if item != "null":
leftNumber = int(item)
node.left = TreeNode(leftNumber)
nodeQueue.append(node.left)
if index >= len(inputValues):
break
item = inputValues[index]
index = index + 1
if item != "null":
rightNumber = int(item)
node.right = TreeNode(rightNumber)
nodeQueue.append(node.right)
return root
import json
def integerListToString(nums, len_of_list=None):
ifnot len_of_list:
len_of_list = len(nums)
return json.dumps(nums[:len_of_list])
def main():
import sys
import io
# 实现了交互功能def readlines():
for line in io.TextIOWrapper(sys.stdin.buffer, encoding=‘utf-8‘):
yield line.strip(‘\n‘)
lines = readlines()
while True:
try:
line = next(lines)
root = stringToTreeNode(line);
ret = Solution().inorderTraversal(root)
out = integerListToString(ret);
except StopIteration:
breakif__name__ == ‘__main__‘:
main()
原文:https://www.cnblogs.com/xxswkl/p/11922021.html
内容总结
以上是互联网集市为您收集整理的二叉树的中序遍历全部内容,希望文章能够帮你解决二叉树的中序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。