潍坊昌大建设集团有限公司网站,大淘客网站上的推广怎么做,临沂展厅设计公司,网页即时聊天110.平衡二叉树
分析#xff1a;判断每个节点的左右子树的高度差小于等于1#xff1b;所以首先需要求左右子树高度#xff0c;再在父节点进行判断#xff0c;故此采用后序遍历。
思路#xff1a;后序遍历二叉树#xff0c;从底部递归回来时加上高度
class Solution {
…110.平衡二叉树
分析判断每个节点的左右子树的高度差小于等于1所以首先需要求左右子树高度再在父节点进行判断故此采用后序遍历。
思路后序遍历二叉树从底部递归回来时加上高度
class Solution {
public:int judge(TreeNode*root){if(rootnullptr)return 0;int hljudge(root-left);if(hl-1) return -1;int hrjudge(root-right);if(hr-1) return -1;if(abs(hr-hl)1) return -1;return 1max(hr,hl);}bool isBalanced(TreeNode* root) {//思路二递归遍历每一个节点的左右子树高度判断是否差值小于等于1if(rootnullptr)return true;return judge(root)-1?false:true;}
257.二叉树的所有路径
思路要找到每一个叶子节点并且加上一路上的值使用前序遍历在遍历到left和right为空时添加路径
class Solution {
public:vectorstringnodes;void judge(TreeNode*root,string mid){if(rootnullptr)return;if(!mid.empty())//当mid中有值时mid-;midto_string(root-val);if(root-leftnullptr root-rightnullptr)nodes.push_back(mid);judge(root-left,mid);judge(root-right,mid);}vectorstring binaryTreePaths(TreeNode* root) {//这题需要从根结点开始遍历且加上val值所以采用前序遍历string mid;judge(root,mid);return nodes;}
};
404.左叶子之和 思路:直接递归遍历判断到左叶子节点计数
class Solution {
public:int count0;void judge(TreeNode*root,bool dis){//dis用来判断是左子节点还是右子节点if(rootnullptr)return;if(root-leftnullptr root-rightnullptr dis)//当该节点是左叶子节点时countroot-val;judge(root-left,true);judge(root-right,false);}int sumOfLeftLeaves(TreeNode* root) {if(root-leftnullptr root-rightnullptr)//考虑只有一个节点的情况return 0;judge(root,true);return count;}
};
