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

110.平衡二叉树

题目

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

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

示例 1:

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

返回 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. 二叉树的所有路径

题目

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

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

示例:?

思考

看到题目中这图就能发现，用层序不行，得用前序遍历，但存在一个问题，判断完一条路径后怎么回到根结点判断另一条路径呢，这里就要用到回溯的思想，不能等到遍历到底了再回头，得遍历一个结点就回头一次，用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.左叶子之和

题目

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

示例：

思考

本题用层序遍历就能解了，但需要注意的是这里是左叶子，也就是在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;

? ? }

};