代码随想录刷题随记15-二叉树回溯

代码随想录刷题随记15-二叉树回溯

110.平衡二叉树

leetcode链接
一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
求深度和求高度的区别：
求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
递归：
所以这里的递归其实是后序遍历的思路

class Solution {
public:void subjudge(bool & isbalanced,int&height ,TreeNode * root){if(root==nullptr){isbalanced=true;height=0;return;}    int heightleft,heightright;bool ifleftb,ifrightb;       subjudge(ifleftb, heightleft, root->left);subjudge(ifrightb, heightright, root->right);if((ifleftb &&ifrightb)&&(abs(heightleft-heightright)<=1))isbalanced=true;elseisbalanced=false;height=heightleft>heightright?heightleft+1:heightright+1;}bool isBalanced(TreeNode* root) {bool isbalanced;int height;subjudge(isbalanced,height,root);return isbalanced;}
};

此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

例如：都知道回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法！

257. 二叉树的所有路径

leetcode链接

class Solution {
public:void sub(TreeNode* root,vector<int>&path,vector<string>& ret){if(root!=nullptr)path.push_back(root->val);if(root->left==nullptr&&root->right==nullptr){string tmp="";for(int i=0;i<path.size()-1;i++){tmp+=to_string(path[i]);tmp += "->";}tmp+=to_string(path[path.size()-1]);ret.push_back(tmp);return;}if(root->left!=nullptr){sub(root->left,path,ret);path.pop_back();//回溯}if(root->right!=nullptr){sub(root->right,path,ret);path.pop_back();//回溯}return;}vector<string> binaryTreePaths(TreeNode* root) {vector<string> ret;vector<int> path;if(root==nullptr)return {};sub(root,path,ret);return ret;}
};

迭代版本

404.左叶子之和

leetcode链接

class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> ret;stack<string> stackPath;stack<TreeNode*> stackNode;if(root==nullptr)return {};stackNode.push(root);stackPath.push("");while(!stackNode.empty()){TreeNode * cur=stackNode.top();stackNode.pop();string path=stackPath.top();stackPath.pop();            path+=to_string(cur->val); path+="->";if(cur->left==nullptr&&cur->right==nullptr){path.pop_back();path.pop_back();ret.push_back(path);}if(cur->left!=nullptr){stackNode.push(cur->left);stackPath.push(path);}if(cur->right!=nullptr){stackNode.push(cur->right);stackPath.push(path);}         }return ret;}
};

404.左叶子之和

leetcode链接
当前节点没法判断自己是不是左叶子，必须要通过节点的父节点来判断其左孩子是不是左叶子。
判断代码如下：

if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {左叶子节点处理逻辑
}

class Solution {
public:void sub(TreeNode * root,int& sum){if(root==nullptr)return;if(root->right!=nullptr){sub(root->right,sum);}if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr){sum+=root->left->val;return;}if(root->left!=nullptr){sub(root->left,sum);}  }int sumOfLeftLeaves(TreeNode* root) {int sum=0;sub(root,sum);return sum;}
};

迭代法
本题迭代法使用前中后序都是可以的，只要把左叶子节点统计出来，就可以了

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum=0;stack<TreeNode*>mystack;if(root==nullptr)return 0;mystack.push(root);while(!mystack.empty()){TreeNode * cur=mystack.top();mystack.pop();if(cur->right!=nullptr){mystack.push(cur->right);}if(cur->left!=nullptr&&cur->left->left==nullptr&&cur->left->right==nullptr){sum+=cur->left->val;continue;}if(cur->left!=nullptr){mystack.push(cur->left);}}return sum;}
};