labuladong的算法小抄之js实现-第0章-学习算法和刷题的框架思维

//二叉树
/**
 * 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;
}

// N叉数
// class TreeNode {
//   constructor(val, children) {
//     this.val = val;
//     this.children = children;
//   }
// }

// 二叉树遍历
// function traverse(root) {
//   //   console.log(root.val); // 前序
//   if (root.left) traverse(root.left);
//   console.log(root.val); // 中序

//   if (root.right) traverse(root.right);
//   //   console.log(root.num); // 后序
// }

// function traverse(root) {
//   console.log(root.val);
//   if (root.children == null || root.children.length == 0) return;
//   for (let i = 0; i < root.children.length; i++) {
//     traverse(root.children[i]);
//   }
// }

// let left = new TreeNode(2);
// let right = new TreeNode(3);
// let root = new TreeNode(1, left, right);
// traverse(root);

// let child1 = new TreeNode(2, null);
// let child2 = new TreeNode(3, null);
// let root = new TreeNode(1, [child1, child2]);
// traverse(root);

// 求二叉树中最大路径和

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
  let ans = -Infinity;
  var oneSideMax = function (root) {
    if (root === null) return 0;
    let left = Math.max(0, oneSideMax(root.left));
    let right = Math.max(0, oneSideMax(root.right));
    ans = Math.max(ans, left + right + root.val);
    return Math.max(left, right) + root.val;
  };
  oneSideMax(root);
  return ans;
};

// 根据前序遍历和中序遍历的结果还原一棵二叉树
var buildTree = function (preorder, inorder) {
  return recover(
    preorder,
    0,
    preorder.length - 1,
    inorder,
    0,
    inorder.length - 1
  );
};

var recover = function (preArray, preStart, preEnd, inArray, inStart, inEnd) {
  if (preStart > preEnd || inStart > inEnd) return null;
  let root = new TreeNode(preArray[preStart]);
  let inRoot = inArray.indexOf(root.val);
  let leftNum = inRoot - inStart;
  root.left = recover(
    preArray,
    preStart + 1,
    preStart + leftNum,
    inArray,
    inStart,
    inRoot - 1
  );
  root.right = recover(
    preArray,
    preStart + leftNum + 1,
    preEnd,
    inArray,
    inRoot + 1,
    inEnd
  );
  return root;
};

//恢复二叉搜索树

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */

var recoverTree = function (root) {
  let prev = null;
  let first = null;
  let second = null;
  const traverse = function (root) {
    if (!root) return;
    traverse(root.left);

    if (prev && root.val < prev.val) {
      second = second == null ? prev : second;
      first = root;
    }
    prev = root;
    traverse(root.right);
  };
  traverse(root);
  let temp = first.val;
  first.val = second.val;
  second.val = temp;
};