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

解析

1)这个问题在介绍二叉树结构的时候,就提到过,不过是直接print()打印的;

2)乍看上去本题也是要打印,但其实是要返回顺序的数值,所以不得不多包一层方法;

3)核心思想还是中序遍历,即左中右的顺序;

4)最好理解的方法,就是递归,另外还可以用栈结构,难度会稍大一点。

代码示例

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        return self.traversal(root, res)

    def traversal(self, node, res):
        if node:
            self.traversal(node.left, res)
            res.append(node.val)
            self.traversal(node.right, res)
        return res

执行用时:32 ms, 在所有 Python3 提交中击败了 89.93% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/368