代码随想录day17 二叉树的高度与深度

2024-01-02 17:39:53

110.平衡二叉树

题目

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

110.平衡二叉树

返回 true 。

思考

本题想用层序,发现行不通,难点在于不知道啥时候记录左右子树的高度,因为会存在当前结点左子树为空但右子树的左子树存在的情况,所以本题用后序递归遍历左右中的思想比较好做,每次递归分别求出左右子树高度然后判断其高度差。

代码

// 后序遍历,本题用层序不好做

class Solution {

public:

? ? int getHeight(TreeNode* node) {

? ? ? ? if(node == nullptr) return 0;

? ? ? ? int leftHeight = getHeight(node->left);

? ? ? ? if (leftHeight == -1) return -1;

? ? ? ? int rightHeight = getHeight(node->right);

? ? ? ? if (rightHeight == -1) return -1;

? ? ? ? if (abs(leftHeight - rightHeight) > 1) return -1;

? ? ? ? else return (1+ max(leftHeight, rightHeight));

? ? }

? ? bool isBalanced(TreeNode* root) {

? ? ? ? int height = getHeight(root);

? ? ? ? if (height == -1) return false;

? ? ? ? else return true;

? ? }

};

257. 二叉树的所有路径

题目

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:?

257.二叉树的所有路径1

思考

看到题目中这图就能发现,用层序不行,得用前序遍历,但存在一个问题,判断完一条路径后怎么回到根结点判断另一条路径呢,这里就要用到回溯的思想,不能等到遍历到底了再回头,得遍历一个结点就回头一次,用vector把遍历过的结点都存起来,并且用到递归的思想,向左时递归左边,向右时递归右边,当向左与向左都为空时,就把vector里的元素拼接成一个string

代码

class Solution {

public:

? ? void traversal(TreeNode* node, vector<int>& path, vector<string>& res) {

? ? ? ? path.push_back(node->val);

? ? ? ? if(node->left == nullptr && node->right == nullptr) {

? ? ? ? ? ? string s;

? ? ? ? ? ? for(int i = 0; i < path.size() - 1; i++) {

? ? ? ? ? ? ? ? s += (to_string(path[i]) + "->");

? ? ? ? ? ? }

? ? ? ? ? ? s += to_string(path[path.size() - 1]);

? ? ? ? ? ? res.push_back(s);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? if (node -> left) {

? ? ? ? ? ? traversal(node->left, path, res);

? ? ? ? ? ? path.pop_back();//回溯关键点,遍历一个往回弹一个

? ? ? ? }

? ? ? ? if(node->right) {

? ? ? ? ? ? traversal(node->right, path, res);

? ? ? ? ? ? path.pop_back(); ? ? ? ? ? ?

? ? ? ? }

? ? }

? ? vector<string> binaryTreePaths(TreeNode* root) {

? ? ? ? vector<string> result;

? ? ? ? vector<int> v;

? ? ? ? if(root == nullptr) return result;

? ? ? ? traversal(root, v, result);

? ? ? ? return result;

? ? }

};

404.左叶子之和

题目

计算给定二叉树的所有左叶子之和。

示例:

404.左叶子之和1

思考

本题用层序遍历就能解了,但需要注意的是这里是左叶子,也就是在node->left时要判断它的左右子树都为空才能算作左叶子。

代码

// 层序遍历

class Solution {

public:

? ? int sumOfLeftLeaves(TreeNode* root) {

? ? ? ? queue<TreeNode*> que;

? ? ? ? if(root == nullptr) return 0;

? ? ? ? que.push(root);

? ? ? ? int sum = 0;

? ? ? ? while(!que.empty()) {

? ? ? ? ? ? int size = que.size();

? ? ? ? ? ? while(size--) {

? ? ? ? ? ? ? ? TreeNode* node = que.front();

? ? ? ? ? ? ? ? que.pop();

? ? ? ? ? ? ? ? if(node->left) {

? ? ? ? ? ? ? ? ? ? que.push(node->left);

? ? ? ? ? ? ? ? ? ? if(!node->left->left && !node->left->right) sum += node->left->val;//叶结点是高度为1的结点,它的左右子树都为空

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(node->right) que.push(node->right);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return sum;

? ? }

};

文章来源:https://blog.csdn.net/2301_80817427/article/details/135339891
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。