94. 二叉树的中序遍历 | LeetCode算法题解

题目描述

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

示例:略

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

思路

用一个栈记录遍历的节点。用一个节点游标指向，从根节点开始，若节点不为空，则把左子树继续入栈，节点为空时，则取出栈顶节点，记录节点值，指向右子树继续遍历。

解法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = root => {
  const result = [];

  if (!root) return result;

  const stack = [];
  let node = root;

  while (node || stack.length) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop();
      result.push(node.val);
      node = node.right;
    }
  }

  return result;
};