大连网页网站制作,建立自我追求无我,中国建设承包商网站,网站底部友情链接代码代码随想录刷题随记15-二叉树回溯
110.平衡二叉树
leetcode链接 一棵高度平衡二叉树定义为#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 求深度和求高度的区别#xff1a; 求深度可以从上到下去查 所以需要前序遍历#xff08;中左右#xff…代码随想录刷题随记15-二叉树回溯
110.平衡二叉树
leetcode链接 一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 求深度和求高度的区别 求深度可以从上到下去查 所以需要前序遍历中左右而高度只能从下到上去查所以只能后序遍历左右中 递归 所以这里的递归其实是后序遍历的思路
class Solution {
public:void subjudge(bool isbalanced,intheight ,TreeNode * root){if(rootnullptr){isbalancedtrue;height0;return;} int heightleft,heightright;bool ifleftb,ifrightb; subjudge(ifleftb, heightleft, root-left);subjudge(ifrightb, heightright, root-right);if((ifleftb ifrightb)(abs(heightleft-heightright)1))isbalancedtrue;elseisbalancedfalse;heightheightleftheightright?heightleft1:heightright1;}bool isBalanced(TreeNode* root) {bool isbalanced;int height;subjudge(isbalanced,height,root);return isbalanced;}
};此题用迭代法其实效率很低因为没有很好的模拟回溯的过程所以迭代法有很多重复的计算。虽然理论上所有的递归都可以用迭代来实现但是有的场景难度可能比较大。
例如都知道回溯法其实就是递归但是很少人用迭代的方式去实现回溯算法
257. 二叉树的所有路径
leetcode链接
class Solution {
public:void sub(TreeNode* root,vectorintpath,vectorstring ret){if(root!nullptr)path.push_back(root-val);if(root-leftnullptrroot-rightnullptr){string tmp;for(int i0;ipath.size()-1;i){tmpto_string(path[i]);tmp -;}tmpto_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;}vectorstring binaryTreePaths(TreeNode* root) {vectorstring ret;vectorint path;if(rootnullptr)return {};sub(root,path,ret);return ret;}
};迭代版本
404.左叶子之和
leetcode链接
class Solution {
public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring ret;stackstring stackPath;stackTreeNode* stackNode;if(rootnullptr)return {};stackNode.push(root);stackPath.push();while(!stackNode.empty()){TreeNode * curstackNode.top();stackNode.pop();string pathstackPath.top();stackPath.pop(); pathto_string(cur-val); path-;if(cur-leftnullptrcur-rightnullptr){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(rootnullptr)return;if(root-right!nullptr){sub(root-right,sum);}if(root-left!nullptrroot-left-leftnullptrroot-left-rightnullptr){sumroot-left-val;return;}if(root-left!nullptr){sub(root-left,sum);} }int sumOfLeftLeaves(TreeNode* root) {int sum0;sub(root,sum);return sum;}
};迭代法 本题迭代法使用前中后序都是可以的只要把左叶子节点统计出来就可以了
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum0;stackTreeNode*mystack;if(rootnullptr)return 0;mystack.push(root);while(!mystack.empty()){TreeNode * curmystack.top();mystack.pop();if(cur-right!nullptr){mystack.push(cur-right);}if(cur-left!nullptrcur-left-leftnullptrcur-left-rightnullptr){sumcur-left-val;continue;}if(cur-left!nullptr){mystack.push(cur-left);}}return sum;}
};
