二叉树常见思路

// 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)
}

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

// 二叉树所有节点+1
void plusOne(TreeNode root) {
    if (root == null) return;
    root.val += 1;

    plusOne(root.left);
    plusOne(root.right);
}
// 判断两颗二叉树完全相同
boolean isSameTree(TreeNode root1, TreeNode root2) {
    // 都为空的话，显然相同
    if (root1 == null && root2 == null) return true;
    // 一个为空，一个非空，显然不同
    if (root1 == null || root2 == null) return false;
    // 两个都非空，但 val 不一样也不行
    if (root1.val != root2.val) return false;

    // root1 和 root2 该比的都比完了
    return isSameTree(root1.left, root2.left)
        && isSameTree(root1.right, root2.right);
}

二叉搜索树BST

判断BST合法性

// 递归
var isValidBST = function (root) {
  return helper(root, null, null);
};
var helper = function (root, min, max) {
  if (root == null) return true;
  if (min != null && root.val <= min.val) return false;
  if (max != null && root.val >= max.val) return false;
  return helper(root.left, min, root) && helper(root.right, root, max);
}
// 中序遍历

在BST中查找一个数是否存在

var searchBST = function (root, val) {
  if (!root) return root;
  if (root.val === val) return root;
  return root.val < val ? searchBST(root.right, val) : searchBST(root.left, val)
};

针对BST的遍历框架

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target)
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

在BST中插入一个数

var insertIntoBST = function (root, val) {
  if (root == null) return new TreeNode(val);
  if (root.val < val)
    root.right = insertIntoBST(root.right, val)
  if (root.val > val)
    root.left = insertIntoBST(root.left, val)
  return root
};

在BST中删除一个数

1. 节点为末端节点，直接删除

2. 节点只有一个非空节点，让该节点顶替自己的位置

3. 节点下有两个子节点，找到左子数中最大的或右子数中最小的节点顶替自己

var deleteNode = function (root, key) {
  if (root == null) return null;
  if (root.val == key) {
    if (root.left == null) return root.right;
    if (root.right == null) return root.left;
    const minNode = getMin(root.right);
    root.val = minNode.val;
    root.right = deleteNode(root.right, minNode.val);
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key);
  } else if (root.val > key) {
    root.left = deleteNode(root.left, key);
  }
  return root;
};

var getMin = function (node) {
  while (node.left !== null) {
    node = node.left;
  }
  return node;
}

翻转二叉树

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

填充每个节点的下一侧右侧节点指针

var connect = function (root) {
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
};

var connectTwoNode = function (node1, node2) {
    if (node1 == null || node2 == null) return;
    node1.next = node2;
    // 相同父节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 跨越父节点
    connectTwoNode(node1.right, node2.left);
}