二叉树面试题

前端精髓

共 2321字,需浏览 5分钟

 ·

2022-03-04 22:24


合并二叉树

function mergeTrees(t1, t2) {  if (t1 == null)    return t2;  if (t2 == null)    return t1;  t1.value += t2.value;  let left = mergeTrees(t1.left, t2.left);  if (left) {    t1.left = left  }  let right = mergeTrees(t1.right, t2.right);  if (right) {    t1.right = right  }  return t1;}console.log(mergeTrees(rootA, rootB))


判断对称二叉树

function isSymmetric (root) {  return isMirror(root, root)}
function isMirror (t1, t2) { if (t1 == null && t2 == null) return true; if (t1 == null || t2 == null) return false; return (t1.value === t2.value) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)}
console.log(isSymmetric(node1))


二叉树翻转

function reverse(node) {  if (node != null) {    let temp = node.left;    node.left = node.right;    node.right = temp;    reverse(node.left);    reverse(node.right);  }}


二叉树的最大深度

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


二叉树的最小深度

function minDepth (root) {  if (root === null) {    return 0  }  return 1 + Math.min(minDepth(root.left), minDepth(root.right))}


路径总和

function hasPathSum (root, sum) {  if (root == null) {    return false  }  if (root.left == null && root.right == null) {    return root.value === sum  }  return hasPathSum(root.left, sum - root.value) || hasPathSum(root.right, sum - root.value)}


平衡二叉树

function isBalanced(root) {  return height(root) >= 0}
function height(root) { if (root === null) { return 0 } let leftHeight = height(root.left) let rightHeight = height(root.right) if (leftHeight === -1 || rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) { return -1 } else { return Math.max(leftHeight, rightHeight) + 1 }}


将有序数组转换为二叉树

// 尽量构建一个平衡二叉树,使元素均匀分布function solution(nums) {  function TreeNode(value) {    this.value = value    this.left = null    this.right = null  }  function arrayToBST(nums, start, end) {    if (end < start) {      return null    }    let mid = (start + end) >> 1    let root = new TreeNode(nums[mid])    root.left = arrayToBST(nums, start, mid - 1)    root.right = arrayToBST(nums, mid + 1, end)    return root  }  return arrayToBST(nums, 0, nums.length - 1)}
console.log(solution([-10, -3, 0, 5, 9]))


浏览 22
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报