搜索二叉树

一种特殊有序的二叉树。如果一棵树不为空，并且如果它的根节点左子树不为空，那么它左子树上面的所有节点的值都小于它的根节点的值，如果它的右子树不为空，那么它右子树任意节点的值都大于他的根节点的值，它的左右子树也是二叉搜索树。

验证是否是搜索二叉树

leetcode上的题目：验证二叉搜索树

通过二叉树的中序遍历判断

var isValidBST = function (root) {
  let pre = -Infinity
  return valid(root)

  function valid(root) {
    if (!root) return true
    if (!valid(root.left)) return false
    if (root.val <= pre) return false
    pre = root.val
    return valid(root.right)
  }
};

完全二叉树

叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

宽度优先遍历

使用队列实现

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

let root = new TreeNode(5)
root.left = new TreeNode(1)
root.right = new TreeNode(4)
root.right.left = new TreeNode(3)
root.right.right = new TreeNode(6)

function traverse(root) {
  const queue = []
  queue.push(root)
  while (queue.length) {
    root = queue.shift()
    console.log(root.val)
    if (root.left) queue.push(root.left)
    if (root.right) queue.push(root.right)
  }
}

traverse(root) //5 1 4 3 6

验证完全二叉树

xxxxxxxxxx25 1const arr = [1, 2, 3, 4, 6, 8, 11, 17, 23, 24, 30]23function find(arr, num) {4 if (!Array.isArray(arr) || arr.length === 0) {5 return false6 }7 let l = 08 let r = arr.length - 19 while (l <= r) {10 let mid = Math.floor((l + r) / 2)11 if (arr[mid] === num) {12 return true13 } else if (arr[mid] < num) {14 l = mid + 115 } else {16 r = mid - 117 }18 }19 return false20}2122console.log(find(arr,3))//true23console.log(find(arr,13))//false24console.log(find(arr,23))//true25console.log(find(arr,33))//falsejs

二叉树最大深度

leetcode上的题目：二叉树的最大深度

递归解决：（树的最大深度等于左右子树的最大深度加一）

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

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

递归解决：（所有节点的左右子树是满二叉树且深度相等）

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

let root = new TreeNode(5)
root.left = new TreeNode(1)
root.right = new TreeNode(4)
root.right.left = new TreeNode(3)
root.right.right = new TreeNode(6)
root.left.left = new TreeNode(6)
root.left.right = new TreeNode(6)

function isFull(root) {
  return depth(root) >= 0

  function depth(root) {
    if (!root) return 0
    let leftDepth = depth(root.left)
    let rightDepth = depth(root.right)
    if (leftDepth !== -1 && leftDepth === rightDepth)
      return leftDepth + 1
    else 
      return -1
  }
}

console.log(isFull(root)) //true

平衡二叉树

任意节点的子树的高度差都小于等于 1

leetcode上的题目：平衡二叉树

递归解决：

var isBalanced = function (root) {
  return depth(root) >= 0

  function depth(root) {
    if (!root) return 0
    let leftDepth = depth(root.left)
    let rightDepth = depth(root.right)
    if (leftDepth !== -1 && rightDepth !== -1 && Math.abs(leftDepth - rightDepth) <= 1) {
      return Math.max(leftDepth, rightDepth) + 1
    } else {
      return -1
    }
  }
};

二叉树共同祖先

leetcode上的题目：二叉树的最近公共祖先

递归解决：

var lowestCommonAncestor = function (root, p, q) {
  if (!root || root === p || root === q) {
    return root
  }
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)
  //if (!left && !right) return null
  if (left && right) return root
  return left ? left : right
};

前驱节点、后继节点

二叉树的前驱节点：就是中序遍历中该节点的前一个节点

二叉树的后继节点：就是中序遍历中该节点的后一个节点

序列化和反序列化

leetcode上的题目：二叉树的序列化与反序列化

//序列化
var serialize = function (root) {
  if (!root) return '#_'
  let result = root.val + '_'
  result += serialize(root.left)
  result += serialize(root.right)
  return result
};

//反序列化
var deserialize = function (data) {
  const arr = data.split('_')

  function createTree(arr) {
    const val = arr.shift()
    if (val === '#') {
      return null
    }
    const head = new TreeNode(val)
    head.left = createTree(arr)
    head.right = createTree(arr)
    return head
  }

  return createTree(arr)
};