Sikara

leecode94---二叉树中序遍历

leecode94—二叉树中序遍历

  • 思路

    1. 递归（左，中，右）
    /**
 * 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 = []
  inorderF(result,root)
  return result
};
/**
 * @param {TreeNode} root
* @param {number[]} result
* @return {number[]}
  */
function inorderF(result,root) {
  //判断空结点
  if (root === null){return}
  //left
  inorderF(result,root.left)
  //root
  result.push(root.val)
  //right
  inorderF(result,root.right)
}

    • 解析：先理解中序遍历：左子树-根节点-右子树；针对最小子树这种情况单独分析：再借助递归思想，其实我们可以发现递归到最后都会只剩一个节点，然后返回上一个节点的位置，因此我们只需要

      image-20220412155625193

      • 一开始我们是处在1节点，但按照中序遍历我们其实是需要先从左边开始，也就是我们需要切换成2节点位置（因为我们可以发现递归这种形式，遍历到最后都会只剩一个节点，然后当前函数执行完毕是会返回到上一个节点的位置），处在2位置，我们看成一个更小的子树，左为空不作为，根节点有效存值，右为空不作为，然后返回上一级函数，执行相同的操作，这就是中序遍历递归做法的核心
    1. 迭代：在递归基础上多加一个栈存放遍历节点的顺序，都是先遍历树到最左边直到不能遍历，在栈里提取上一次节点的位置，存储结果，接着换到该位置的右节点位置继续按照上述步骤遍历，当右节点也为空时但此时栈不为空（意为着还有节点的右子树还未遍历），就继续在栈里提取上一次节点的位置，存储结果，又换到该位置的右节点位置继续遍历，最终栈为空，（右）节点也为空就是遍历完成
    //迭代解法
var inorderTraversal = function(root) {
  const res = [];
  const stk = [];
  while (root || stk.length) {
    while (root) {
      stk.push(root);
      root = root.left;
    }
    root = stk.pop();
    res.push(root.val);
    root = root.right;
  }
  return res;
};

Sikara

© 2025 Sikara