LeetCode 94：二叉树的中序遍历 Binary Tree Inorder Traversal

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

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

示例:

输入: [1,null,2,3]
   1
    
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

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

百度百科：二叉树的中序遍历：https://baike.baidu.com/item/中序遍历

遍历顺序：左子节点 --> 根节点 --> 右子节点

如下所示的二叉树：

A
     /   
   BC
 /       /  
D    E   F    G

其遍历顺序为：D -> B -> E -> A ->F -> C -> G

二叉树遍历可以用 DFS（深度优先搜索）完成，其实现方式为：递归或借助数据结构 栈 迭代。

这种遍历方式本质上是一个先进后出的栈式遍历方式，递归方法实际也是用递归方式实现栈的先进后出。

Java：

class Solution {
    public List inorderTraversal(TreeNode root) {
 List list = new ArrayList<>();//数组
 dfs_recursion(root, list);//传入递归函数
 return list;
    }

    private void dfs_recursion(TreeNode node, List list) {
 if (node == null) return;//基线条件
 dfs_recursion(node.left, list);//先遍历左子节点
 list.add(node.val);//遍历到左子节点的顶点，取出该节点的值
 dfs_recursion(node.right, list);//递归遍历右节点
    }
}

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
 #数组
 res = list()
 #传入递归函数
 self.dfs_recursion(root, res)
 return res

    def dfs_recursion(self, node: TreeNode, res: List[int]):
 #基线条件
 if not node: return
 #递归遍历左子节点
 self.dfs_recursion(node.left, res)
 #取顶点节点的值
 res.append(node.val)
 #递归遍历右子节点
 self.dfs_recursion(node.right, res)

class Solution {
    public List inorderTraversal(TreeNode root) {
 List list = new ArrayList<>();//数组
 if (root == null) return list;
 Stack stack = new Stack<>();//用数据结构栈暂存节点
 TreeNode cur = root;//定义当前节点
 while (!stack.isEmpty() || cur != null) {//循环条件：栈不空或当前节点不空
     if (cur != null) {//当前节点不空时
  stack.push(cur);//当前节点入栈
  cur = cur.left;//刷新当前节点
     } else {//当前节点空时
  cur = stack.pop();//当前节点的父节点出栈
  list.add(cur.val);//数组存入节点的值
  cur = cur.right;刷新当前节点
     }
 }
 return list;
    }
}

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
 #初始化数组、栈
 res, stack = list(), list()
 #当前节点指向根节点
 cur = root
 #递归条件为：栈或当前节点非空
 while stack or cur:
     if cur:
  #当前节点非空时入栈
  stack.append(cur)
  #刷新当前节点
  cur = cur.left
     else:
  #当前节点为空时其父节点出栈
  cur = stack.pop()
  #其值存入数组
  res.append(cur.val)
  #刷新当前节点
  cur =cur.right
 return res