[Leetcode][python]Binary Tree Inorder Traversal/二叉树的中序遍历

Dear 丶 2022-06-11 02:23 108阅读 0赞

## 题目大意 ##

中序遍历一个二叉树

**挑战**：不用递归只用迭代做

## 解题思路 ##

递归思路：简单

迭代思路：[参考][Link 1]

我们使用一个栈来解决问题。步骤如下：

1
    
    　　　　　　　　　　　　　　　/　  \
    
    　　　　　　　　　　　　　　 2　　  3
    
    　　　　　　　　　　　　　  /   \　 /   \
    
       　　　　　　　　　　　　4     5  6    7

一，我们将根节点1入栈，如果有左孩子，依次入栈，那么入栈顺序为：1，2，4。由于4的左子树为空，停止入栈，此时栈为\{1，2，4\}。

二，此时将4出栈，并遍历4，由于4也没有右孩子，那么根据中序遍历的规则，我们显然应该继续遍历4的父亲2，情况是这样。所以我们继续将2出栈并遍历2，2存在右孩子，将5入栈，此时栈为\{1，5\}。

三，5没有孩子，则将5出栈并遍历5，这也符合中序遍历的规则。此时栈为\{1\}。

四，1有右孩子，则将1出栈并遍历1，然后将右孩子3入栈，并继续以上三个步骤即可。

栈的变化过程：\{1\}->\{1,2\}->\{1,2,4\}->\{1,2\}->\{1\}->\{1,5\}->\{1\}->\{\}->\{3\}->\{3,6\}->\{3\}->\{\}->\{7\}->\{\}。

## 代码 ##

### 递归 ###

class Solution(object):
        def generate(self, root, result):
            if root:
                self.inorder(root.left, list)
                result.append(root.val)
                self.inorder(root.right, list)
        def inorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            if not root:
                return []
            result = []
            self.generate(root, result)
            return result

### 递归（极简代码） ###

class Solution(object):
        def inorderTraversal(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            if not root:
                return []
            else:
                return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

### 迭代 ###

和前序后序不同，需要遵循上面的思路

class Solution:
        # @param root, a tree node
        # @return a list of integers
        def inorderTraversal(self, root):
            result = []
            stack = []
            while root or stack:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    root = stack.pop()
                    result.append(root.val)
                    root = root.right
            return result

## 总结 ##

1.  Python中：\[1\]+\[2\]+\[3\] = \[1,2,3\]

[Link 1]: http://www.cnblogs.com/zuoyuan/p/3720273.html