中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。
中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树

示例

[二叉树] 系列：非递归中序遍历 - 图1

方法一：递归

  1. class Solution {
  2.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> inorderTraversal(TreeNode root) {
  4.         if(root == null)  return res;
  5.         inorderTraversal(root.left);
  6.         res.add(root.val);
  7.         inorderTraversal(root.right);
  8.         return res;
  9.     }
  10. }

方法二：迭代

1.初始化返回列表，判空，初始化栈，初始化cur节点
2.循环：当前节点不空或者栈不空

  • 当前节点不空：从当前节点开始一直往左相继入栈
  • 判断当栈不空，出栈，同时添加到res，当前节点指向右孩子

3.返回res

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root == null) return res;
  5.         LinkedList<TreeNode> stack = new LinkedList<>();
  6.         TreeNode cur = root;
  7.         while(cur != null || !stack.isEmpty()){
  8.             while(cur != null){
  9.                 stack.addFirst(cur);
  10.                 cur = cur.left;
  11.             }
  12.             if(!stack.isEmpty()){
  13.                 cur = stack.removeFirst();
  14.                 res.add(cur.val);
  15.                 cur = cur.right;
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. }

方法三：Morris中序遍历

能将非递归的中序遍历空间复杂度降为 O(1)。