代码随想录三刷 day17 | 二叉树之110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和

本文主要是介绍代码随想录三刷 day17 | 二叉树之110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三刷day17

- - 110.平衡二叉树
  - 257. 二叉树的所有路径
  - 404.左叶子之和

110.平衡二叉树

题目链接
解题思路： 求高度用后续遍历，先得到左子树和右子树的情况，然后再进行判断（左右中）使用递归遍历
代码如下：

class Solution {
public:// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1int getHeight(TreeNode* node) {if (node == NULL) {return 0;}int leftHeight = getHeight(node->left); // 左if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right); // 右if (rightHeight == -1) return -1;int result;if (abs(leftHeight - rightHeight) > 1) {  // 中result = -1;} else {result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度}return result;}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}};

257. 二叉树的所有路径

题目链接
解题思路：
代码如下：

class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};

404.左叶子之和

题目链接
解题思路：
左叶子的定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
递归三部曲

确定递归函数的参数和返回值

判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int

使用题目中给出的函数就可以了。

确定终止条件

如果遍历到空节点，那么左叶子值一定是0

if (root == NULL) return 0;

注意，只有当前遍历的节点是父节点，才能判断其子节点是不是左叶子。所以如果当前遍历的节点是叶子节点，那其左叶子也必定是0，那么终止条件为：

if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0;

确定单层递归的逻辑

当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和右子树左叶子之和，相加便是整个树的左叶子之和。

代码如下：

int leftValue = sumOfLeftLeaves(root->left);    // 左
if (root->left && !root->left->left && !root->left->right) {leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right);  // 右int sum = leftValue + rightValue;               // 中
return sum;

整体递归代码如下：

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right== NULL) return 0;int leftValue = sumOfLeftLeaves(root->left);    // 左if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况leftValue = root->left->val;}int rightValue = sumOfLeftLeaves(root->right);  // 右int sum = leftValue + rightValue;               // 中return sum;}
};