【LeetCode with Python】 94. Binary Tree Inorder Traversal

题目

原题页面:https://leetcode.com/problems/binary-tree-inorder-traversal/
本文地址:http://leetcode.xnerv.wang/binary-tree-inorder-traversal/
题目类型:Tree, Hash Table, Stack
难度评价:Medium
类似题目:(M) Validate Binary Search Tree, (M) Binary Tree Preorder Traversal, (H) Binary Tree Postorder Traversal, (M) Binary Search Tree Iterator, (M) Kth Smallest Element in a BST, (H) Closest Binary Search Tree Value II, (M) Inorder Successor in BST

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

For example:
Given binary tree {1,#,2,3},
1
\
2
/
3

return [1,3,2].

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

confused what "{1,#,2,3}" means?
OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

1
/ \
2 3
/
4
\
5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".


分析

非递归中序遍历二叉树,每一个计算机和软件专业的朋友大学上数据结构时都会遇到的题之一。总结成一句话就是:有左节点时将左节点压栈,无左节点时出栈一个元素(栈如果是空的则遍历结束),输出该元素,然后如果该元素有右节点则将cur指针跳到该右节点。
关键在于还是要理解计算机递归的实现原理,然后用程序去加以模拟和实现。例如这题,就可以参考中序遍历二叉树的递归版本,在脑海中模拟一下整个递归过程,即子调用的进入和退出的顺序,就能知道应该用一个栈去模拟这个过程,并且何时入栈和何时出栈。


代码

class Solution:

    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):

        if None == root:
            return [ ]

        list = [ ]
        stack = [ ]
        cur = root
        stack.append(cur)

        while True:
            if None != cur and None != cur.left:
                stack.append(cur.left)
                cur = cur.left
                continue
            if len(stack) >= 1:
                cur = stack.pop()
                list.append(cur.val)
                cur = cur.right
            else:
                break
            if None != cur:
                stack.append(cur)

        return list

results matching ""

    No results matching ""