依然是每道题都有递归和迭代2种解法，都是基于遍历的递归和迭代方法，第2道涉及回溯。目前还是对基础的集中遍历方法不熟悉，尤其是与深度、高度或其他问题的关系。一些情况只能对应一种遍历方式，另一些问题用多种遍历方式均可以解决，需要明确题目所求的目标具体是哪一种情况。
第1题（110.平衡二叉树）自己的思路是用后序遍历求当前节点的最大深度（即树的高度），首先判断左、右两子节点是不是平衡二叉树，如果不是，那么当前树也不是；如果是，则根据左、右两子节点的深度之差是否满足不大于1来返回true或false。
class Solution {
public:
int getDepth(TreeNode *cur, int depth) {
if (cur == nullptr) {
return depth;
}
int depthLeft = getDepth(cur->left, depth + 1);
int depthRight = getDepth(cur->right, depth + 1);
return max(depthLeft, depthRight);
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
if (isBalanced(root->left) && isBalanced(root->right)) {
if (abs(getDepth(root->left, 0) - getDepth(root->right, 0)) <= 1) {
return true;
}
return false;
}
return false;
}
};代码虽然AC，但所用的“后序遍历计算深度”不够规范，因为这里的“后序遍历计算深度”在每次深度变深时不会更新当前深度，而是会在到达叶子节点后向上回溯，每个返回值都是最大深度，那么回溯过程就是多余、没有必要的。所以标准的方式还是：
- 后序遍历计算高度（因为有了子节点的高度，便得到当前节点高度为最高子节点高度 + 1）；
- 前序遍历计算深度（因为有了父节点的深度，便得到当前子节点深度为父节点深度 + 1）。
相关的代码都在前一天的博客当中。看了题解后，了解到这一题要根据高度进行判断，所以应该用后序遍历计算高度。所以关键问题变成了如何在遍历的过程中标记树不平衡的情况，因为树高度都是自然数，所以可以用-1来标记。实现中需要注意在计算左/右子树高度后，需要判断其返回值是不是-1，如果是，就说明左/右子树不满足要求，要立即return -1，否则在最后return时，会错误返回一个自然数，导致判断错误。
class Solution {
public:
int getDepth(TreeNode *cur) {
if (cur == nullptr) {
return 0;
}
int depthLeft = getDepth(cur->left);
if (depthLeft == -1) {
return -1;
}
int depthRight = getDepth(cur->right);
if (depthRight == -1) {
return -1;
}
if (abs(depthLeft - depthRight) > 1) {
return -1;
}
return 1 + max(depthLeft, depthRight);
}
bool isBalanced(TreeNode* root) {
if (getDepth(root) == -1) {
return false;
}
return true;
}
};这道题的迭代解法分2各部分：
- 用栈进行先序遍历，判断每个节点是否满足要求；
- 对于每个节点，计算其高度（最大深度），方式采用“利用栈模拟的后序遍历”。由于要计算深度，所以需要在层数+1/-1时有相应的标记。又因为统一写法的迭代遍历会对中节点有空指针标记，所以采用统一写法的后序遍历迭代。这里不能使用前序或中序遍历，因为需要在中间节点出栈时令depth减1，而如果使用前序或中序遍历，此时中间节点的右、左节点或右节点还在栈中，它们充当中间节点时depth已经错误地减掉1了。
class Solution {
public:
int getDepth(TreeNode *cur) {
if (cur == nullptr) {
return 0;
}
stack<TreeNode*> st;
st.push(cur);
int res = 0, depth = 0;
while (!st.empty()) {
cur = st.top();
st.pop();
if (cur != nullptr) {
depth++;
st.push(cur);
st.push(nullptr);
if (cur->right) {
st.push(cur->right);
}
if (cur->left) {
st.push(cur->left);
}
}
else {
cur = st.top();
st.pop();
depth--;
}
res = max(res, depth);
}
return res;
}
bool isBalanced(TreeNode* root) {
if (root == nullptr) {
return true;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
if (abs(getDepth(cur->left) - getDepth(cur->right)) > 1) {
return false;
}
if (cur->left) {
st.push(cur->left);
}
if (cur->right) {
st.push(cur->right);
}
}
return true;
}
};需要注意getDepth()中while()进行的条件仅是栈非空，而没有cur不为空指针，要与非统一方式的中序遍历区别开。题解中所使用的计算当前节点深度的迭代方法是用栈来模拟后序遍历，但其实用层序遍历也可计算：
int getDepth(TreeNode *cur) {
if (cur == nullptr) {
return 0;
}
int depth = 0;
queue<TreeNode*> que;
que.push(cur);
while (!que.empty()) {
depth++;
int size = que.size();
for (int i = 0; i < size; ++i) {
cur = que.front();
que.pop();
if (cur->left) {
que.push(cur->left);
}
if (cur->right) {
que.push(cur->right);
}
}
}
return depth;
}第2题（257. 二叉树的所有路径）自己没想到解法，只知道应该用前序遍历的回溯方法。在看了题解的递归函数形式后，写出了AC的代码。递归的函数参数有3个，分别是当前节点，用于保存当前路径的vector<int> path，用于保存多条路径结果的vector<string> res。那么终止条件即为当前节点无子节点时，将当前path中内容转为string并放入res中。之后再对当前节点的左、右子节点递归即可。
class Solution {
public:
void traversal(TreeNode *cur, vector<int> path, vector<string>& res) {
path.push_back(cur->val);
if (cur->left == nullptr && cur->right == nullptr) {
string s = "";
for (int i = 0; i < path.size(); ++i) {
if (i != 0) {
s += "->";
}
s += to_string(path[i]);
}
res.push_back(s);
return;
}
if (cur->left) {
traversal(cur->left, path, res);
}
if (cur->right) {
traversal(cur->right, path, res);
}
return;
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (root == nullptr) {
return res;
}
traversal(root, vector<int>(), res);
return res;
}
};注意这一版本的traversal()中path为非引用类型，在传入函数时只做拷贝，其本身的值不会被改变，所以在左、右节点递归之后不用对path做回退操作，也就没有显式的回溯过程，但回溯仍然是存在的。下面版本的代码显式地进行了回溯：
class Solution {
public:
void traversal(TreeNode *cur, vector<int>& path, vector<string>& res) {
path.push_back(cur->val);
if (cur->left == nullptr && cur->right == nullptr) {
string s = "";
for (int i = 0; i < path.size(); ++i) {
if (i != 0) {
s += "->";
}
s += to_string(path[i]);
}
res.push_back(s);
return;
}
if (cur->left) {
traversal(cur->left, path, res);
path.pop_back();
}
if (cur->right) {
traversal(cur->right, path, res);
path.pop_back();
}
return;
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (root == nullptr) {
return res;
}
vector<int> path;
traversal(root, path, res);
return res;
}
};此外，实现过程中也学习到string与int相互转化用to_string()和atoi()。
迭代法自己也没想到解法，看了题解发现也不难。在用栈实现前序遍历的基础上 ，只需要用到一个额外的栈来保存路径，其入栈和出栈时机、内容都与前序遍历的节点栈保持一致，然后在遇到叶子节点（无子节点的节点）时将路径栈中内容存入res。
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
if (root == nullptr) {
return res;
}
stack<TreeNode*> stTree;
stack<string> stPath;
stTree.push(root);
stPath.push(to_string(root->val));
while (!stTree.empty()) {
TreeNode *cur = stTree.top();
stTree.pop();
string path = stPath.top();
stPath.pop();
if (cur->left == nullptr && cur->right == nullptr) {
res.push_back(path);
}
if (cur->right) {
stTree.push(cur->right);
stPath.push(path + "->" + to_string(cur->right->val));
}
if (cur->left) {
stTree.push(cur->left);
stPath.push(path + "->" + to_string(cur->left->val));
}
}
return res;
}
};第3题（404.左叶子之和）递归方法方面，自己想到的是对每个节点根据其是左节点还是右节点做标记，再根据其是左还是右节点左不同处理，只有在当前是左节点且为叶子节点时才返回当前节点值，否则就返回当前节点的左节点的递归，与右节点的递归的和。
class Solution {
public:
int sum(TreeNode *cur, bool isLeft) {
if (cur == nullptr) {
return 0;
}
if (isLeft && cur->left == nullptr && cur->right == nullptr) {
return cur->val;
}
return sum(cur->left, true) + sum(cur->right, false);
}
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return sum(root->left, true) + sum(root->right, false);
}
};递归解法的题解思路较常规，参数只有当前节点。由于当前节点是否为左节点无法判断，只能判断当前节点的左节点是左节点，所以在满足：
- 当前节点存在左子节点；
- 当前节点的左子节点无子节点。
那么就说明当前节点的左子节点是左叶子节点，其val是当前节点左子树的左叶子节点和。再对右子节点递归即可。否则就要对左、右子节点都进行递归。
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 0;
}
if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {
return root->left->val + sumOfLeftLeaves(root->right);
}
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};代码中7~9行的判断去掉也不影响结果，当会使递归多一层。
在有了递归法题解思路的基础上，迭代法就比较容易了，使用前中后和层序遍历都可以，只需要在遍历途中，将满足递归法中判断左叶子节点所用条件的节点值加起来，就能得到所有左叶子节点和。
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
stack<TreeNode*> stTree;
stTree.push(root);
int sum = 0;
while (!stTree.empty()) {
TreeNode *cur = stTree.top();
stTree.pop();
if (cur->left != nullptr && cur->left->left == nullptr && cur->left->right == nullptr) {
sum += cur->left->val;
}
if (cur->right) {
stTree.push(cur->right);
}
if (cur->left) {
stTree.push(cur->left);
}
}
return sum;
}
};