94. 二叉树的中序遍历

发表于 分类于 阅读次数：

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：
root = new TreeNode(1,null,null);
root.left = new TreeNode(2,null,null);
root.left.left = new TreeNode(4,null,null);
root.left.right = new TreeNode(5,null,null);
root.right = new TreeNode(3,null,null);
root.right.left = new TreeNode(6,null,null);
root.right.right = new TreeNode(9,null,null);

输出: [4, 2, 5, 1, 6, 3, 9]

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 */

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let result = [];
  let inorder = (root) => {
    if (!root) return null;
    inorder(root.left);
    result.push(root.val);
    inorder(root.right);
  };
  inorder(root);
  return result;
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var inorderTraversal = function (root) {
  let result = [];
  let stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    result.push(root.val);
    root = root.right;
  }
  return result;
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var inorderTraversal = function (root) {
  let result = [];
  let stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    result.push(root.val);
    root = root.right;
  }
  return result;
};

morris 遍历

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)。
Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 cur。):

  1. 如果 cur 无左孩子，cur 向右移动（cur=cur.right），加入结果。
  2. 如果 cur 有左孩子，找到 cur 左子树上最右的节点，记为 mostright:
    • 如果 mostright 的 right 指针指向空，让其指向 cur，cur 向左移动（cur=cur.left）
    • 如果 mostright 的 right 指针指向 cur，让其指向空，cur加入结果，cur 向右移动（cur=cur.right）
  3. 重复上述操作，直至访问完整棵树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var inorderTraversal = function (root) {
  const res = [];
  let cur = root;
  let mostRight = null;
  while (cur) {
    if (cur.left) {
      // mostRight 节点就是当前 cur 节点向左走一步，然后一直向右走至无法走为止
      mostRight = cur.left;
      while (mostRight.right && mostRight.right !== cur) {
        mostRight = mostRight.right;
      }

      // mostRight的右孩子指向空，让其指向cur，cur向左移动
      if (!mostRight.right) {
        mostRight.right = cur;
        cur = cur.left;
      } else {
        // 说明左子树已经访问完了，我们需要断开链接
        // mostRight的右孩子指向cur，让其指向空，cur向右移动
        res.push(cur.val);
        mostRight.right = null;
        cur = cur.right;
      }
    } else {
      // 如果没有左孩子，则直接访问右孩子
      res.push(cur.val);
      cur = cur.right;
    }
  }
  return res;
};