建设大型网站,阿里云主机wordpress,猎头公司排行,wordpress joomla seo110.平衡二叉树 力扣题目链接 给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。 本题中#xff0c;一棵高度平衡二叉树定义为#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示… 110.平衡二叉树 力扣题目链接 给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 返回 false 。 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。但leetcode中强调的深度和高度很明显是按照节点来计算的如图 var isBalancedfunction(root){if(rootnull) return true;if(Math.abs(getHeight(root.left)-getHeight(root.right))1) return false;return isBalanced(root.left)isBalanced(root.right);
}
var getHeightfunction(root){if(rootnull) return 0;return Math.max(getHeight(root.left),getHeight(root.right))1;
}
// 代码随想录
// 递归法
var isBalanced function(root) {//还是用递归三部曲 后序遍历 左右中 当前左子树右子树高度相差大于1就返回-1// 1. 确定递归函数参数以及返回值const getDepth function(node) {// 2. 确定递归函数终止条件if(node null) return 0;// 3. 确定单层递归逻辑let leftDepth getDepth(node.left); //左子树高度// 当判定左子树不为平衡二叉树时,即可直接返回-1if(leftDepth -1) return -1;let rightDepth getDepth(node.right); //右子树高度// 当判定右子树不为平衡二叉树时,即可直接返回-1if(rightDepth -1) return -1;if(Math.abs(leftDepth - rightDepth) 1) {return -1;} else {return 1 Math.max(leftDepth, rightDepth);}}return !(getDepth(root) -1);
};
// 迭代法
// 获取当前节点的高度
//getHeight函数的作用是获取当前节点的高度
var getHeight function (curNode) {let queue [];if (curNode ! null) queue.push(curNode); // 压入当前元素let depth 0, res 0;while (queue.length) {let node queue[queue.length - 1]; // 取出栈顶if (node ! null) {queue.pop();queue.push(node); // 中queue.push(null);depth;node.right queue.push(node.right); // 右node.left queue.push(node.left); // 左} else {queue.pop();node queue[queue.length - 1];queue.pop();depth--;}res res depth ? res : depth;}return res;
}
var isBalanced function (root) {if (root null) return true;let queue [root];while (queue.length) {let node queue[queue.length - 1]; // 取出栈顶queue.pop(); if (Math.abs(getHeight(node.left) - getHeight(node.right)) 1) {return false;}node.right queue.push(node.right);node.left queue.push(node.left);}return true;
}; 257. 二叉树的所有路径 力扣题目链接(opens new window) 给定一个二叉树返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 var binaryTreePaths function(root) {if(rootnull) return [];if(root.leftnullroot.rightnull) return [root.val.toString()];let left_pathsbinaryTreePaths(root.left);let right_pathsbinaryTreePaths(root.right);let paths[];for(let path of left_paths){paths.push(root.val.toString()-path);}for(let path of right_paths){paths.push(root.val.toString()-path);}return paths;
}
// 代码随想录
// 递归法
var binaryTreePaths function(root) {//递归遍历递归三部曲let res [];//1. 确定递归函数 函数参数const getPath function(node,curPath) {//2. 确定终止条件到叶子节点就终止if(node.left null node.right null) {curPath node.val;res.push(curPath);return;}//3. 确定单层递归逻辑curPath node.val -;node.left getPath(node.left, curPath);node.right getPath(node.right, curPath);}getPath(root, );return res;};
// 迭代法
var binaryTreePaths function(root) {if (!root) return [];const stack [root], paths [], res [];while (stack.length) {const node stack.pop();let path paths.pop();if (!node.left !node.right) { // 到叶子节点终止, 添加路径到结果中res.push(path node.val);continue;}path node.val -;if (node.right) { // 右节点存在stack.push(node.right);paths.push(path);}if (node.left) { // 左节点存在stack.push(node.left);paths.push(path);}}return res;}; #404.左叶子之和 力扣题目链接 计算给定二叉树的所有左叶子之和。 var sumOfLeftLeavesfunction(root){if(rootnull) return 0;let sum0;if(root.left!nullroot.left.leftnullroot.left.rightnull){sumroot.left.val;}sumsumOfLeftLeaves(root.left);sumsumOfLeftLeaves(root.right);return sum;
}
// 代码随想录
// 递归法
var sumOfLeftLeaves function(root) {//采用后序遍历 递归遍历// 1. 确定递归函数参数const nodesSum function(node) {// 2. 确定终止条件if(node null) {return 0;}let leftValue nodesSum(node.left);let rightValue nodesSum(node.right);// 3. 单层递归逻辑let midValue 0;if(node.left node.left.left null node.left.right null) {midValue node.left.val;}let sum midValue leftValue rightValue;return sum;}return nodesSum(root);
};
// 迭代法
var sumOfLeftLeaves function(root) {//采用层序遍历if(root null) {return null;}let queue [];let sum 0;queue.push(root);while(queue.length) {let node queue.shift();if(node.left ! null node.left.left null node.left.right null) {sumnode.left.val;}node.left queue.push(node.left);node.right queue.push(node.right);}return sum;};
