二叉树相关算法题

树或者链表的题大部分是要靠递归来做的。

第一题：翻转二叉树

分析：针对每个节点都要进行同样的操作，左子树和右子树互换，当到达最后的叶子节点终止。

// function TreeNode (x) {
//   this.val = x;
//   this.left = null;
//   this.right = null;
// }
function Mirror (root) {
  // 定义翻转函数
  function swap (node) {
    if (!node) return;
    // 使用解构赋值进行左右节点交换
    [node.left, node.right] = [node.right, node.left];
    // 递归，对子节点进行相同操作
    swap(node.left);
    swap(node.right);
  }
  return swap(root);
}

知识点：二叉树的几种遍历方式

前序遍历：root left right
中序遍历：left root right
后序遍历：left right root

第二题：从前序与中序遍历序列构造二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

分析：
1、在前序遍历找到根节点 root。
2、在中序遍历中，根节点左侧的{4,7,2}就是 left 节点，右侧{5,3,8,6}是 right 节点。
3、前序遍历的{2,4,7}按照规则，2 是 root…以此类推。

// function TreeNode (x) {
//   this.val = x;
//   this.left = null;
//   this.right = null;
// }
// 前序遍历：preorder = [1,2,4,7,3,5,6,8];
// 中序遍历：inorder = [4,7,2,1,5,3,8,6];
function reConstructBinaryTree (preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;  // 递归终止条件
  let rootVal = preorder[0];        // 1.从前序遍历找到根节点
  let root = new TreeNode(rootVal); // 构造根节点
  let i = inorder.findIndex(e => e === rootVal);  // 2.在中序遍历找到根节点的索引
  // let i = inorder.indexOf(rootVal);
  // 3.划分左子树和右子树
  // 中序遍历：root 的左边是左子树，用 inorder.slice(0, i) 截取，右子树用 inorder.slice(i+1) 截取。
  // 前序遍历：root 后面 i 项都是左子树，用 preorder.slice(1, i+1) 截取，从 i+1 项都是右子树，用 preorder.slice(i+1) 截取。
  // 截取到的子数组又分别符合前序遍历和中序遍历规律，所以递归
  root.left = reConstructBinaryTree(preorder.slice(1, i+1), inorder.slice(0, i));
  root.right = reConstructBinaryTree(preorder.slice(i+1), inorder.slice(i+1));
  return root;
}

第三题：从中序与后序遍历序列构造二叉树

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

// 中序遍历 inorder = [9,3,15,20,7]
// 后序遍历 postorder = [9,15,7,20,3]
function buildTree (inorder, postorder) {
  if (!inorder.length || !postorder.length) return null;
  let rootVal = postorder[postorder.length-1];  // 后序最后一项
  // 创建根节点
  let root = new TreeNode(rootVal);
  // 查找根节点在中序遍历索引
  let i = inorder.indexOf(rootVal);   // i=1
  // 划分左子树与右子树
  root.left = buildTree(inorder.slice(0, i), postorder.slice(0, i));
  root.right = buildTree(inorder.slice(i+1), postorder.slice(i, postorder.length-1));
  return root;
}

第四题：从前序与后序遍历序列构造二叉树

前序遍历 preorder = [1,2,4,5,3,6,7] root left right
后序遍历 postorder = [4,5,2,6,7,3,1] left right root

分析：要怎么划分左子树和右子树？
根据前序遍历的第一个左节点来划分，就是题中的 2。

function constructFromPrePost = function (pre, post) {
  if (!pre.length || !post.length) return null;
  let rootVal = pre[0];
  let root = new TreeNode(rootVal);
  if (pre.length < 1) return null;
  let i = post.indexOf(pre[1]);   // 前序遍历中第一个左节点索引
  root.left = constructFromPrePost(pre.slice(1, i+2), post.slice(0, i+1));
  root.right = constructFromPrePost(pre.slice(i+2), post.slice(i+1, post.length-1));
  return root;
}

第五题：二叉树的最大深度和最小深度

最大深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

function maxDepth (root) {
  if (root === null) return 0;
  let lefth = maxDepth(root.left);
  let righth = maxDepth(root.right);
  return Math.max(lefth, righth) + 1;
}

最小深度

function minDepth (root) {
  if (root === null) return 0;
  let leftm = minDepth(root.left);
  let rightm = minDepth(root.right);
  if (!root.left || !root.right) return Math.max(leftm, right) + 1;
  return Math.min(leftm, right) + 1;
}