题目: 给定一个二叉树, 返回它的中序遍历.
法一: 网上的代码
思路: 利用栈的递归, 对每次取的节点进行标记, 第一次遍历该节点时, 标记为灰色, 左子树和右子树标记为白色, 注意入栈的顺序是右 中 左, 因为最后存储的顺序的左 中 右.
- # 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: continue
- if 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]
- if not 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):
- if not 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:
- break
- if __name__ == '__main__':
- main()
- View Code
来源: http://www.bubuko.com/infodetail-3301705.html