算法训练营第二十天 | LeetCode 110平衡二叉树、LeetCode 257 二叉树的所有路径、LeetCode 404 左叶子之和

LeetCode 110 平衡二叉树

递归写法很简单，直接自底向上每个节点判断是否为空，为空说明该层高度为0。不为空用一个int型变量l记录左子树高度（递归调用该函数自身），一个int型变量r记录右子树高度（同样递归调用该函数自身），将l和r相减取绝对值，大于1说明不平衡直接返回-1，此外还需要判断l和r是否已经是-1，这种情况下也直接返回-1。这样判断的底层原理是计算每个节点返回值是高度还是-1，取-1也是因为不会影响到正常高度的计算。最后来到递归遍历阶段，返回1+max(l,r)即可。

这个过程中，最上层是确认返回条件，中间是确认参数和返回值，最下层是递归逻辑。

代码如下：

class Solution {
public:int height(TreeNode* root) {if (!root) return 0; int l = height(root->left), r = height(root->right);if (abs(l - r) > 1) return -1;else if (l == -1) return -1;else if (r == -1) return -1;return 1 + max(l, r); }bool isBalanced(TreeNode* root) {if (height(root) != -1) return true;else return false;}
};

LeetCode 257 二叉树的所有路径

这题对于学过回溯法的人来说，很明显是回溯了。新手可能会有点头痛。

回溯法本质上也是一种递归，是一种暴力枚举。在递归过程中，如果没有后续状态就会把当前这一条路径放进存储结果的集合中，返回当前函数到上一层。而如果有后续状态，就先记录当前路径，将当前路径加上其中一个下一状态，用这一路径继续递归，直到返回，在其语句后面还要将路径还原至递归前。相当于先给你一个苹果，让你吃完之后看苹果是啥样子，记录下来，再一路回到你吃苹果之前，把苹果给别人吃，看又是啥样子。这样的递归过程就能实现一种暴力枚举。

代码如下：

class Solution {
private:vector<string> res;string path = "";
public:void backtracking(TreeNode* cur) {if (!cur->left && !cur->right) {res.push_back(path);}else {if (cur) {string temp = path;if (cur->left) {string s = to_string(cur->left->val);path += "->";path += s;backtracking(cur->left);path = temp;}if (cur->right) {string s = to_string(cur->right->val);path += "->";path += s;backtracking(cur->right);path = temp;}}}}vector<string> binaryTreePaths(TreeNode* root) {if (!root) return res;string s = to_string(root->val);path += s;backtracking(root);return res;}};

还需要注意的有递归起始状态，返回条件和每次递归逻辑的确定。

本题还可以尝试迭代法来写。暂时先放这，等会来写。

LeetCode 404 左叶子之和

其实前序遍历等遍历方式中选一种就行了，需要注意的是左叶子首先要是某个叶子的左节点，然后还要是叶子节点。可以顺便满足这个遍历情况的，前序遍历是肯定可以的。中序遍历也可以，层序遍历和后续遍历会比较麻烦一点。这里给出前序遍历实现的代码如下：

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum = 0;TreeNode* cur = root;queue<TreeNode*> myque;while (cur || !myque.empty()) {while (cur) {myque.push(cur);if (cur->left) {if (!cur->left->left && !cur->left->right)sum += cur->left->val;}cur = cur->left;}cur = myque.front();myque.pop();cur = cur->right;}return sum;}
};