【Q002】😈第一部分：二叉树😈94. 二叉树的中序遍历

[fly0o0]

94. 二叉树的中序遍历

awesome-coding-js

验证使用，生成一棵树

function Node(val, left, right) {
  this.val = val
  this.left = left
  this.right = right
}

function Tree() {
  this.root = null
}

Tree.prototype = {
  insert(val) {
    const node = new Node(val, null, null)
    if (!this.root) {
      this.root = node
      return
    }
    let current = this.root
    let parent = null
    while (current) {
      parent = current
      if (val < parent.val) {
        current = current.left
        if (!current) {
          parent.left = node
          return
        }
      } else {
        current = current.right
        if (!current) {
          parent.right = node
          return
        }
      }

    }
  }
}

const t = new Tree()
t.insert(4)
t.insert(2)
t.insert(6)
t.insert(3)
t.insert(1)
t.insert(5)
t.insert(7)
// 树的形状
//     4
//   2   6
//  1 3 5 7

[fly0o0]

递归

function inorder(node, res = []) {
  if (node) {
    middOrder(node.left, res)
    res.push(node.val)
    middOrder(node.right, res)
  }
  return res
}

标记法

  /**
   * 利用标志位判断是否访问过
   *
   * @param {*} root
   */
  function inorderTraversal(root) {
    // WHITE - 未访问的新结点； GRAY - 已访问的结点
    const [WHITE, GRAY] = [0, 1]
    const stack = [[WHITE, root]]
    const res = []

    let color, node

    while (stack.length) {
      // 若栈中有元素，则按照左节点、根节点、右节点的顺序依次弹出元素
      [color, node] = stack.pop()

      if (!node) continue

      // 当前指向的结点是未访问过的结点，将其右节点，根节点，左节点依次入栈
      if (color === WHITE) {
        stack.push([WHITE, node.right])
        stack.push([GRAY, node])
        stack.push([WHITE, node.left])
      } else {
        res.push(node.val)
      }
    }
    return res
  }

模拟递归栈

/**
 * 模拟递归栈
 *
 * @param {*} node
 */
function inorderTraversal(root) {
  const stack = []
  const queue = []

  while (stack.length !== 0 || root) {
    // 存在节点
    if (root) {
      // 保持父节点
      stack.push(root)
      // 找下一个左节点
      root = root.left
      // 没有存在节点
    } else {
      // 获取父节点
      root = stack.pop()
      // 打印当前节点
      queue.push(root.val)
      // 找一下右节点
      root = root.right
    }
  }

  return queue
}

[Yelingxiao]

const inorderTraversal = function (root) {
  const result = []
  const stack = []
  while (stack.length || root) {
    if (root) {
      stack.push(root)
      root = root.left
    } else {
      root = stack.pop()
      result.push(root.val)
      root = root.right
    }
  }
  return result
}

[Yelingxiao]

function Node (value) {
  this.value = value
}
function insertNode (tree, value) {
  let node = tree
  let key = null
  while (node.value !== value) {
    key = value < node.value ? 'left' : 'right'
    if (!node[key]) {
      node[key] = new Node(value)
      break
    }
    node = node[key]
  }
  return tree
}
const array = [1, null, 2, 3]
const tree = array.reduce((t, v) => t ? insertNode(t, v) : new Node(v), null)

[harvest-L]

// 递归

var inorderTraversal = function(root, result = []) {
    if (!root) {
        return [];
    }
    inorderTraversal(root.left, result);
    result.push(root.val);
    inorderTraversal(root.right, result);
    return result;
};

// 循环

var inorderTraversal = function(root) {
    if (!root) {
        return [];
    }
    let stack = [];
    let result = [];
    while(root || stack.length) {
        if (root) {
            stack.push(root);
            root = root.left;
        } else {
            let node = stack.pop();
            result.push(node.val);
            root = node.right;
        }

    }
    return result;
};

[CookGuo]

var inorderTraversal = function(root) {
    // 保留结果
    let result = []
    // 左子树的缓存
    let stck = []
    let current = root
    while(stck.length > 0 || current) {
        // 一直找到最左子节点
        while(current) {
            stck.push(current)
            current = current.left
        }
        // 最左出栈
        current = stck.pop();
        result.push(current.val);
        // 看是否有右节点
        current = current.right;
    }
    return result
};

[OceanApart]

/**
 * 递归
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  if (root) {
    /* 遍历左子树 + 当前节点值 + 遍历右子树  */
    return inorderTraversal(root.left).concat([ root.val ], inorderTraversal(root.right))
  } else {
    return []
  }
};

/**
 * 迭代
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  const result = []
  const stack = [] // 遍历栈
  let current // 当前节点

  if (root) {
    stack.push(root)
  }

  while(stack.length) {
    current = stack.pop()

    if (current) {
      /* 如果左子树存在 */
      if (current.left) {
        stack.push(current) // 当前节点入栈
        stack.push(current.left) // 左子树入栈

        current.left = null // 清空当前节点的左子树
      } else {
        result.push(current.val) // 记录当前节点值
        stack.push(current.right) // 右子树入栈
      }
    }
  }

  return result
};