二叉树

第k小元素

题目

给定一棵二叉搜索树，请找出其中的第k小的结点。 例如，（5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

const tree = {
  val: 5,
  left: {
    val: 3,
    left: {
      val: 2
    },
    right: {
      val: 4
    }
  },
  right: {
    val: 7,
    left: {
      val: 6
    },
    right: {
      val: 8
    }
  }
}

const min = (root, k) => {
  const traverse = (node) => {
    if (node.left) {
      // 如果拿到了结果就 return
      const result = traverse(node.left)
      if (result) return result
    }

    // 实际的操作点
    k = k - 1
    if (k === 0) {
      return node.val
    }

    if (node.right) {
      // 如果拿到了结果就 return
      const result = traverse(node.right)
      if (result) return result
    }
  }

  return traverse(root, k)
}

console.log(min(tree, 2)) // 3
console.log(min(tree, 3)) // 4
console.log(min(tree, 4)) // 5

二叉树的最大深度

const tree = {
  val: 5,
  left: {
    val: 3,
    left: {
      val: 2
    },
    right: {
      val: 4,
    }
  },
  right: {
    val: 7,
    left: {
      val: 6
    },
    right: {
      val: 8,
      right: {
        val: 9
      }
    }
  }
}

const maxDepth = (node) => {
  if (!node) {
    return 0
  }

  if (!node.left && !node.right) {
    return 1
  }

  return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1
}

console.log(maxDepth(tree)) // 4

二叉树层序遍历

题目

const tree = { val: 5, left: { val: 3, left: { val: 2 }, right: { val: 4 } }, right: { val: 8, left: { val: 6, right: { val: 7 } }, right: { val: 9 } } }

// 广度优先遍历
const traverse = (root) => {
  let result = []

  let queue = [root]

  let isReversed = true
  while (queue.length > 0) {
    isReversed = !isReversed
    let count = queue.length
    let tempList = []
    while (count > 0) {
      const node = queue.shift()
      // tempList.push(node.val)
      isReversed ? tempList.unshift(node.val) : tempList.push(node.val)
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
      count -= 1
    }
    result.push(tempList)
  }
  return result
}

// 深度优先遍历
const levelOrder = function (root) {
  let result = []

  const traverse = (node, level) => {
    if (!node) return
    const arr = result[level] || []
    if (level % 2 === 0) {
      arr.push(node.val)
    } else {
      arr.unshift(node.val)
    }
    result[level] = arr
    traverse(node.left, level + 1)
    traverse(node.right, level + 1)
  }

  traverse(root, 0)
  return result
};

前序中序构建二叉树

题目

一个前序数组和一个中序数组，构建成一个二叉树

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


const buildTree = function (preorder, inorder) {
  if (preorder.length === 0) {
    return null
  }

  // 取出第一个
  const cur = preorder.shift()
  const node = new TreeNode(cur)

  const index = inorder.findIndex((item) => {
    return item === node.val
  })

  // 左子树
  node.left = buildTree(preorder.slice(0, index), inorder.slice(0, index))
  // 右子树
  node.right = buildTree(preorder.slice(index), inorder.slice(index + 1))

  return node
};

console.log(' ==> ', buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]));

迭代的方式进行前序遍历

题目

迭代的方式进行前序遍历

const traverse = (root) => {
  let result = []
  let stack = []
  let cur = root
  while (cur || stack.length) {
    // 遍历完左侧内容了
    while (cur) {
      result.push(cur.val)
      stack.push(cur)
      cur = cur.left
    }

    const node = stack.pop()
    cur = node.right
  }
  return result
}

console.log(traverse(tree))

判断二叉树是否合法

题目

判断二叉树是否合法

const tree = {
  val: 3,
  left: {
    val: 1,
    left: {
      val: 0
    },
    right: {
      val: 2
    }
  },
  right: {
    val: 5,
    left: {
      val: 4,
    },
    right: {
      val: 6
    }
  }
}

const isValidBST = function (root) {
  const isValid = (node, min, max) => {
    if (node === null || node === undefined) {
      return true
    }

    // 当前节点 与 左右节点关系
    const is = node.val > min
      && node.val < max
      && isValid(node.left, min, node.val)
      && isValid(node.right, node.val, max)

    return is
  }

  return isValid(root, -Infinity, Infinity)
};

console.log('isValidBST', isValidBST(tree))