94. 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

解法一：递归

# 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]:
        res = []
        self.travel(root, res)
        return res

    def travel(self, root, res):  #辅助函数，注意要将结果集作为参数传入，才能在递归中修改结果集
        if root:
            self.travel(root.left, res)
            res.append(root.val)
            self.travel(root.right, res)

解法二：用栈。

递归是用函数栈保存信息，因此非递归也要用栈，考虑用栈模拟递归过程，即先递归左子树到底，然后访问根，再递归右子树

用一个工作节点p遍历整棵树。思路是先一直进入左子，直到叶节点，期间将所有路途节点入栈。到达最左叶节点后弹栈，进入右子树。

其实到达最左叶节点不用判断stack是否非空，因为外面大循环while已经保证了stack非空

class Solution:
    def inorderTraversal(self, root: TreeNode):
        res = []
        s = []  #栈
        p = root    #工作节点
        while p or s:
            # 找最左子，路上依次入栈
            while p:
                s.append(p)
                p = p.left
            # 走到最左子，弹栈
            p = s.pop()
            res.append(p.val)
            #对右子执行如上操作
            p = p.right
        return res

js：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  const res = []
  let p = root
  const stack = []
  while (p || stack.length > 0) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    p = stack.pop()  // 到达最左叶节点就弹栈，访问该节点
    res.push(p.val)   
    p = p.right  // 访问该节点右子
  }
  return res
};