二叉树面试题
前端精髓
共 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]))
评论