树算法题

二叉树的层序遍历【L102】

1. 递归实现

广度优先搜索：有一个队列，维护当前深度变量，保证入队列的时候左子节点在右子节点前面

var levelOrder = function(root) {
  const res = [];
  function traversal(root, depth) {
    if (root !== null) {
      // 如果这一层级没有的情况下，初始化为空数组
      if (!res[depth]) res[depth] = [];
      res[depth].push(root.val);
      // 保证左子节点在右子节点前面就行，这样入队列的情况下也能保持左右顺序
      traversal(root.left, depth + 1);
      traversal(root.right, depth + 1);
    }
  }
  traversal(root, 0);
  return res;
};

2. 迭代实现

var levelOrder = function(root) {
  /* 非递归的实现方式 */
  let res = [];
  if (root == null) return res;
  let queue = [root];
  // while 循环控制从上向下一层层遍历
  while (queue.length) {
    let size = queue.length;
    // 记录这一层的节点值
    let level = [];
    // for 循环控制每一层从左向右遍历
    for (let i = 0; i < size; i++) {
      let cur = queue.shift();
      level.push(cur.val);
      if (cur.left != null) queue.push(cur.left);
      if (cur.right != null) queue.push(cur.right);
    }
    res.push(level);
  }
  return res;
};

二叉树的前序遍历【L144】

1. 递归实现

var preorderTraversal = function(root, array = []) {
  if (root) {
    array.push(root.val);
    preorderTraversal(root.left, array);
    preorderTraversal(root.right, array);
  }
  return array;
};

2. 迭代实现

var preorderTraversal = function(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      result.push(current.val);
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    current = current.right;
  }
  return result;
};

二叉树的中序遍历【L94】

1. 递归实现

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

2. 迭代实现

var inorderTraversal = function(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
};

二叉树的后序遍历【L145】

1. 递归实现

var postorderTraversal = function(root, array = []) {
  if (root) {
    postorderTraversal(root.left, array);
    postorderTraversal(root.right, array);
    array.push(root.val);
  }
  return array;
};

2. 迭代实现

// 非递归实现：我们需要先遍历右子树，再遍历左子树
var postorderTraversal = function(root) {
  // 初始化数据
  const result = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      result.unshift(root.val); // 添加到数组开头
      root = root.right;
    }
    root = stack.pop();
    root = root.left;
  }
  return result;
};

二叉树的最大深度【L104】

1. 递归实现

时间复杂度：O(n)

var maxDepth = function(root) {
  if (!root) {
    return 0;
  } else {
    const left = maxDepth(root.left);
    const right = maxDepth(root.right);
    return Math.max(left, right) + 1;
  }
};

2. 迭代实现

var maxDepth = function(root) {
  if (root == null) return 0;
  let queue = [];
  queue.push(root);
  let ans = 0;
  while (queue.length) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      // 队头出队列
      let node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    ans += 1;
  }
  return ans;
};

合并二叉树 【L617】

1. 递归实现

var mergeTrees = function(root1, root2) {
  // 如果一棵树有，另一棵树没有，接上去
  if (root1 == null) return root2;
  if (root2 == null) return root1;
  // 两棵树都有的节点，叠加节点值
  root1.val += root2.val;
  // 递归合并左右子树
  root1.left = mergeTrees(root1.left, root2.left);
  root1.right = mergeTrees(root1.right, root2.right);
  return root1;
};

2. 迭代实现

var mergeTrees = function(root1, root2) {
  // 确定终止条件，如果root1 为空，合并后就为root2
  if (!root1) return root2;
  // 确定终止条件，如果root2 为空，合并后就为root1
  if (!root2) return root1;
  const queue = [root1, root2];
  while (queue.length) {
    const node1 = queue.shift();
    const node2 = queue.shift();
    // 此时两个节点一定不为空，val相加
    node1.val += node2.val;
    // 如果两棵树左节点都不为空，加入队列
    if (node1.left !== null && node2.left !== null) {
      queue.push(node1.left);
      queue.push(node2.left);
    }
    // 如果两棵树右节点都不为空，加入队列
    if (node1.right !== null && node2.right !== null) {
      queue.push(node1.right);
      queue.push(node2.right);
    }
    // 当root1的左节点 为空 root2的左节点直接合并
    if (node1.left === null) {
      node1.left = node2.left;
    }
    // 当root1的右节点 为空 root2右节点直接合并
    if (node1.right === null) {
      node1.right = node2.right;
    }
  }
  return root1;
};

二叉搜索树的第 k 大节点【O54】

问题描述：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

解法基于此性质：二叉搜索树的中序遍历为 递增序列，二叉搜索树的中序遍历倒序为 递减序列，第 K 大也就是递减序列数组的 arr[k-1]，

1. 递归-逆中序遍历（右节点->根节点->左节点）

var kthLargest = function(root, k) {
  const arr = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.right);
    arr.push(node.val);
    dfs(node.left);
  }
  dfs(root);

  return arr[k - 1];
};

2. 迭代解法

var kthLargest = function(root, k) {
  // 反向中序遍历
  let stack = [],
    cur = root;
  while (stack.length > 0 || cur != null) {
    while (cur) {
      stack.push(cur);
      cur = cur.right;
    }
    cur = stack.pop();
    k--;
    if (k == 0) {
      return cur.val;
    }

    cur = cur.left;
  }
  return null;
};

翻转二叉树 【L216】

1. 递归

时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

var invertTree = function(root) {
  if (root === null) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};