110.平衡二叉树

题目链接：110.平衡二叉树
求高度，后序遍历。
递归 后序遍历
如果某一节点为非平衡二叉树，则整个二叉树就为非平衡二叉树，可以一直向上层递归-1

class Solution {
public:int recursion(TreeNode* cur) {if (!cur) return 0;//终止条件//左int left = recursion(cur->left);if (left == -1) return -1;//剪枝//右int right = recursion(cur->right);if (right == -1) return -1;//剪枝//中return (abs(left - right) > 1) ?  -1 : 1 + max(left, right);}bool isBalanced(TreeNode* root) {return recursion(root) != -1;}
};

迭代
层序遍历可以求深度（从上往下），但是不能求高度（从下往上）。
层序遍历各个节点，各个节点高度是通过后序遍历求出

class Solution {
public:int getHeight(TreeNode* cur) {stack<TreeNode*> st;if (cur) st.push(cur);int res = 0, height = 0;while (!st.empty()) {TreeNode* tmp = st.top();st.pop();if (tmp) {st.push(tmp); st.push(nullptr);//中++height;if(tmp->right) st.push(tmp->right);//右if(tmp->left) st.push(tmp->left);//左} else {st.pop();//出栈--height;//回溯}res = res > height ? res : height;}return res;}bool isBalanced(TreeNode* root) {stack<TreeNode*> st;if (!root) return true;else st.push(root);while (!st.empty()) {TreeNode* cur = st.top();st.pop();if (abs(getHeight(cur->left) - getHeight(cur->right)) > 1)return false;if (cur->right) st.push(cur->right);if (cur->left) st.push(cur->left);}return true;}
};

回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法！
因为对于回溯算法已经是非常复杂的递归了，如果再用迭代的话，就是自己给自己找麻烦，效率也并不一定高。

---

257. 二叉树的所有路径

题目链接： 257. 二叉树的所有路径
需要用深度遍历来求路径。深度遍历中，使用前序遍历。因为前序遍历的顺序为中左右，先遍历中间节点，再遍历子节点。
因为返回的为走过的路径。当找到第一条路径之后，寻找第二条路径，需要清除第一步路径走过的，直至清除剩余根节点。所以要回溯。
递归 前序遍历 回溯

class Solution {
public:void traversal(TreeNode* cur, vector<int>& path, vector<string>& res) {path.push_back(cur->val);//中if (!cur->left && !cur->right) {//终止条件string tmp;//处理前size-1个元素，留下最后一个元素。因为最后一个元素没有"->"for (int i = 0; i < path.size() - 1; ++i) {tmp += to_string(path[i]);tmp += "->";}res.push_back(tmp + to_string(path[path.size() - 1]));//加上最后一个元素return;}if (cur->left) {//左traversal(cur->left, path, res);path.pop_back();//回溯}if (cur->right) {//右traversal(cur->right, path, res);path.pop_back();//回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;vector<int> path;traversal(root, path, res);return res;}
};

上述代码需要回溯，是因为每条路走完，最后的路径存储到path中，从path中提取int，再统一处理成string形式。
也可以每一步都处理string，而不是最后在统一处理成string，则不需要对path进行回溯。
递归 没有回溯

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

下述代码中，string path不能改为string& path，因为传值时，只操作当前函数中path，传址，则操作整个递归过程中的path。

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

前序遍历，需要多一个辅助stack来保存路径上的节点。为什么要用stack呢，保证与前序遍历相同的处理方式。
迭代 前序遍历

class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;stack<string> stS;//保存路径的节点stack<TreeNode*> stT;stT.push(root);stS.push(to_string(root->val));while (!stT.empty()) {TreeNode* cur = stT.top();stT.pop();//中string path = stS.top();stS.pop();if (!cur->left && !cur->right) {res.push_back(path);}if (cur->right) {//右stT.push(cur->right);stS.push(path + "->" + to_string(cur->right->val));}if (cur->left) {//左stT.push(cur->left);stS.push(path + "->" + to_string(cur->left->val));}}return res;}
};

---

404.左叶子之和

题目链接：404.左叶子之和
判断节点是否为叶子节点，判断该节点左右子节点是否为空。
如何判断节点是否为左叶子，则需要通过该节点的父节点来判断，对于父节点来说，左子节点的左右子节点为空。
递归 后序遍历

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (!root) return 0;if (!root->left && !root->right) return 0;int left = sumOfLeftLeaves(root->left);//左//判断左节点是否为叶子节点if (root->left/*左节点存在*/ && !root->left->left && !root->left->right/*左节点的左右节点不存在*/)left = root->left->val;int right = sumOfLeftLeaves(root->right);//右return left + right;//中}
};

迭代 前序遍历

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;st.push(root);int res = 0;while (!st.empty()) {TreeNode* cur = st.top();//中st.pop();if (cur->left && !cur->left->left && !cur->left->right)res += cur->left->val;if (cur->right) st.push(cur->right);//右if (cur->left) st.push(cur->left);//左}return res;}
};