94. 二叉树中序遍历

题目

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

示例:

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

输出: [1,3,2]

题解

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  var s = [];
  function fn(root) {
    if (!root) return;
    fn(root.left);
    s.push(root.val);
    fn(root.right);
  }
  fn(root);
  return s;
};

时间复杂度：O(n)。递归函数 T(n)=2*T(n/2)+1。 空间复杂度：最坏情况下需要空间 O(n)，平均情况为 O(logn)。

迭代

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

var inorderTraversal = function(root) {
  var res = [];
  //栈
  var s = []; // 只保存左子树
  var p = root;

  while (p || s.length > 0) {
    //直至左节点为空，即没有左节点为止
    while (p) {
      s.push(p);
      p = p.left;
    }
    //出栈，存放根节点
    p = s.pop();
    res.push(p.val);
    p = p.right;
  }
  return res;
};

时间复杂度：O(n)。

空间复杂度：O(n)。