算法题--二叉树中序遍历

image.png

0. 链接

题目链接

1. 题目

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

2. 思路1：递归

• 先左子节点, 后根节点, 再右子节点

3. 代码

# coding:utf8
from typing import  List


# 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) -> List[int]:

        def inorder_traversal(node, results):
            if node is None:
                return

            inorder_traversal(node.left, results)
            results.append(node.val)
            inorder_traversal(node.right, results)

        results = list()
        inorder_traversal(root, results)

        return results


solution = Solution()

root = node = TreeNode(1)
node.right = TreeNode(2)
node = node.right
node.left = TreeNode(3)

print(solution.inorderTraversal(root))

输出结果

[1, 3, 2]

4. 结果

image.png

5. 思路2: 利用栈结构

• 先一路取左节点, 直到不能取为止, 依次压入栈中
• 然后栈顶元素(即最左子节点)出栈, 并加入结果列表中, 然后尝试切换到这个节点的右子树
• 对于每个子树节点, 仍然像对待一棵树一样的处理, 再次循环处理
• 这样就从左下角逐渐处理到根节点, 然后又依次处理右子树

6. 代码

# coding:utf8
from typing import  List


# 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) -> List[int]:
        results = list()
        stack = list()
        cur = root
        while cur is not None or len(stack) > 0:
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            results.append(cur.val)
            cur = cur.right
        return results


solution = Solution()

root = node = TreeNode(1)
node.right = TreeNode(2)
node = node.right
node.left = TreeNode(3)

print(solution.inorderTraversal(root))

输出结果

[1, 3, 2]

结果

image.png