二叉树的中序遍历

Leetcode Link: 94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

题目

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

注意返回的是列表，同时列表元素没有按层数组成新的列表

解法一

思路：参照基于递归的中序遍历，

题解： 这是使用全局变量的方法，基本上就是按从递归序的操作上来的，

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def recur(cur):
            if not cur:
                return []
            
            recur(cur.left)
            res.append(cur.val)
            recur(cur.right)
        
        if not root:
            return []
        res = []
        recur(root)
        return res

使用局部变量的方法，获取到子树的信息后在一起进行处理

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
 
        res = []
        # 中序是 “左中右” 的顺序
        res.extend(left)
        res.append(root.val)
        res.extend(right)
        return res

解法二

思路：迭代

中序遍历_（较难）

创建一个栈，每次：

1. 当前子树的左边界从上到下依次进站
2. 弹出一个节点 cur
3. 对 cur 的右节点重复 1-3 步

你可以看看这个例子

什么是左边界？

一个树，沿着左孩走到没有左孩，这条路径就是左边界。

比如： 上图中的树的左边界为：1 2 4，以节点3为根节点的子树的左边界为 3 6

上图中的树的左边界为 1 2 4，以节点5为根节点的子树的左边界为 5 6 7，以节点3为根节点的子树的左边界为3 8，依次类推。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        self.addLeftBound(stack, root)
        while(len(stack)>0):
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack = self.addLeftBound(stack, cur.right)
        return res
            
    def addLeftBound(self, stack, node):
        while(node):
            stack.append(node)
            node = node.left
        return stack

为什么这么操作就是中序了呢？

因为所有的树都是可以被左边界分解掉的，如下图。 （同理也可以被右边界分解掉） 把左边界放到了栈里去是先头再左，那么弹出的时候就是先左再头。只不过右树是后做的。 换句话说，就是把二叉树按照左边界分解了，只不过右树后做，即

指向原始笔记的链接

解法三

思路：morris 遍历 todo

题解：

启发和联系