哪个程序做下载网站好,鞍山吧最新消息,开个人网站如何赚钱,软件开发网站建设科技有限公司LeetCode 代码随想录跟练 Day15 110.平衡二叉树257.二叉树的所有路径404.左叶子之和222.完全二叉树的节点个数 110.平衡二叉树
题目描述#xff1a; 给定一个二叉树#xff0c;判断它是否是 平衡二叉树 平衡二叉树的定义是#xff0c;对于树中的每个节点#xff0c;其左右… LeetCode 代码随想录跟练 Day15 110.平衡二叉树257.二叉树的所有路径404.左叶子之和222.完全二叉树的节点个数 110.平衡二叉树
题目描述 给定一个二叉树判断它是否是 平衡二叉树 平衡二叉树的定义是对于树中的每个节点其左右子树的高度差不超过1。思路使用递归对比左子树和右子树的高度差是否超过1若超过1则当前节点返回-1作为标示否则返回当前节点的最大深度。代码如下
class Solution {
private:int traverse(TreeNode* root) {if (root nullptr) return 0;int leftHeight traverse(root-left);int rightHeight traverse(root-right);if (leftHeight -1 || rightHeight -1) {return -1;}if (leftHeight - rightHeight 1 || leftHeight - rightHeight -1) {return -1;}return max(leftHeight, rightHeight) 1;}public:bool isBalanced(TreeNode* root) {int height traverse(root);if (height -1) return false;return true;}
};257.二叉树的所有路径
题目描述 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 主要思路为对树进行遍历并将遍历时的当前路径记录并在到达叶子节点后将当前路径添加到结果中。同时在遍历过程中需要对路径的状态实时进行回溯比如从当前节点退出上一个节点的路径中就不应再保留当前节点的信息。这里使用字符串值传递方式可以非显式的实现回溯。代码如下
class Solution {
private:void traverse(TreeNode* root, string path, vectorstring paths) {if (root nullptr) return;if (!path.empty()) path -;path to_string(root-val);if (!root-left !root-right) {paths.push_back(path);return;}traverse(root-left, path, paths);traverse(root-right, path, paths);}public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring res;if (root nullptr) return res;traverse(root, , res);return res;}
};另外使用迭代法进行遍历时原理相同在push节点进入记录节点的stack时同时将当前路径同时push进入记录路径的stack中这样在每次循环获取当前节点时获取到的路径是对应的。注意在分别对左右节点的路径修改时由于存在需要在处理前一个之后继续处理后一个的情况左右节点都不为nullptr所以不能修改path变量而是应该通过临时变量记录路径并入栈。代码如下
class Solution {
public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring res;if (root nullptr) return res;stackTreeNode* nodeStk;stackstring pathStk;nodeStk.push(root);pathStk.push(to_string(root-val));while (!nodeStk.empty()) {TreeNode* cur nodeStk.top(); nodeStk.pop();string path pathStk.top(); pathStk.pop();if (!cur-left !cur-right) {res.push_back(path);continue;}if (cur-left) {nodeStk.push(cur-left);pathStk.push(path - to_string(cur-left-val));}if (cur-right) {nodeStk.push(cur-right);pathStk.push(path - to_string(cur-right-val));}}return res;}
};404.左叶子之和
题目描述 给定二叉树的根节点 root 返回所有左叶子之和。 示例 1 输入: root [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24 示例 2: 输入: root [1] 输出: 0 在遍历时使用isLeft的bool变量标示当前节点是否是上一个状态的左节点在确认叶子节点值时同时需要确保该bool变量为true其余均为遍历框架。代码如下
class Solution {
private:int traverse(TreeNode* root, bool isLeft) {if (root nullptr) return 0;if (!root-left !root-right isLeft) {return root-val;}int left traverse(root-left, true);int right traverse(root-right, false);return left right;}public:int sumOfLeftLeaves(TreeNode* root) {return traverse(root, false);}
};同理可以使用迭代法通过确认左节点的方式若左节点不为nullptr且为叶子节点则记录结果除此之外的所有都不算左叶子。代码如下
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root nullptr) return 0;stackTreeNode* stk;stk.push(root);int res 0;while (!stk.empty()) {TreeNode* cur stk.top(); stk.pop();// 若左节点不为nullptr且为叶子节点if (cur-left !cur-left-left !cur-left-right) {res cur-left-val;}if (cur-left) stk.push(cur-left);if (cur-right) stk.push(cur-right);}return res;}
};222.完全二叉树的节点个数
题目描述 给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。 完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1 1 1~ 2 h 2^h 2h 个节点。 示例 1 输入root [1,2,3,4,5,6] 输出6 示例 2 输入root [] 输出0 示例 3 输入root [1] 输出1 最简单的二叉树遍历计算节点数这里使用层序遍历实现
class Solution {
public:int countNodes(TreeNode* root) {if (root nullptr) return 0;queueTreeNode* q;int res 0;q.push(root);while (!q.empty()) {int size q.size();res size;while (size--) {TreeNode* cur q.front(); q.pop();if (cur-left) q.push(cur-left);if (cur-right) q.push(cur-right);}}return res;}
};由于题中所给为完全二叉树可以根据其特性进行优化完全二叉树的高度可以通过一直向左直到叶子节点确定、完全二叉树的节点树可以通过比较左右子树的高度来判断。 若左子树高度等于右子树根据完全二叉树的性质可知左子树为满二叉树完全二叉树的叶子节点从最左边开始右子树高度相同则表示左边排满了若高度不同相反则表示左子树不满而右子树一定是高度小一行的满二叉树。代码如下
class Solution {
private:int getHeight(TreeNode* node) {int res 0;while (node) {res;node node-left;}return res;}public:int countNodes(TreeNode* root) {if (root nullptr) return 0;int leftHeight getHeight(root-left);int rightHeight getHeight(root-right);if (leftHeight rightHeight) {return (1 leftHeight) countNodes(root-right);} else {return (1 rightHeight) countNodes(root-left);}}
};
