许昌网站建设公司排行榜,做网站运营有前景吗,网站域名有了_网站如何建设,WordPress配置七牛云树形DP#xff1a; Question1: 以X为头结点的树#xff0c;最大距离#xff1a;
1. X不参与#xff0c;在左子树上的最大距离
2. X不参与#xff0c;在右子树上的最大距离
3. X参与#xff0c;左树上最远的结点通过X到右树最远的结点
最后的结果一定是三种情况的最大…树形DP Question1: 以X为头结点的树最大距离
1. X不参与在左子树上的最大距离
2. X不参与在右子树上的最大距离
3. X参与左树上最远的结点通过X到右树最远的结点
最后的结果一定是三种情况的最大值
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Info{public:int maxdistace;int high;Info(int val1 , int val2){maxdistace val1;high val2;}
};class Solution {
public:Info dp(TreeNode* node){if(nodenullptr){return Info(0,0);}Info l dp(node-left);Info r dp(node-right);return Info(max(l.highr.high1 , max(l.maxdistace , r.maxdistace)) , max(l.high,r.high)1);}int diameterOfBinaryTree(TreeNode* root) {Info res dp(root);return res.maxdistace-1;}
};
Question2: 根据某树头结点来或不来进行分类即可
#include iostream
#includebits/stdc.h
using namespace std;class TreeNode{
public:int num;int happy;vectorTreeNode* nexts;TreeNode(int number , int val){num number;happy val;}
};class Info{
public:int inval;int outval;Info(int val1 , int val2){inval val1;outval val2;}
};vectorTreeNode* Happy;Info dp(int cur){if(Happy[cur]-nexts.empty())return Info(Happy[cur]-happy , 0);int inv Happy[cur]-happy;int outv 0;for(auto it:Happy[cur]-nexts){Info temp dp(it-num);inv temp.outval;outv max(temp.inval , temp.outval);}return Info(inv , outv);
}int main() {int n , root;cinnroot;Happy.resize(n);for(int i 1 ; in ; i){int val;cinval;Happy[i-1] new TreeNode(i-1 , val);}for(int i 0 ; in-1 ; i){int up , low;cinuplow;Happy[up-1]-nexts.push_back(Happy[low-1]);}Info res dp(root-1);coutmax(res.inval , res.outval);return 0;
} Morris遍历(时间复杂度O(N) 空间复杂度O(1)) 前序第一次到达一个节点的时候就打印
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;if(rootnullptr)return res;while(root!nullptr){TreeNode* temp root-left;if(temp!nullptr){while(temp-right!nullptrtemp-right!root){temp temp-right;}if(temp-rightnullptr){temp-right root;res.push_back(root-val);root root-left;continue;}else{temp-right nullptr;}}else{res.push_back(root-val);}root root-right;}return res;}
};
中序只能到达一次的节点直接打印能到达两次的第二次打印
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;if(rootnullptr)return res;while(root!nullptr){TreeNode* temp root-left;if(temp!nullptr){while(temp-right!nullptrtemp-right!root){temp temp-right;}if(temp-rightnullptr){temp-right root;root root-left;continue;}else{temp-right nullptr;}}res.push_back(root-val);root root-right;}return res;}
};
后序第二次回到一个节点时逆序打印该节点左子树右边界最后单独逆序打印整棵树右边界
class Solution {
public:TreeNode* reverse(TreeNode* root){TreeNode* pre nullptr;TreeNode* next nullptr;while(root!nullptr){next root-right;root-right pre;pre root;root next;}return pre;}vectorint postorderTraversal(TreeNode* root) {vectorint res;TreeNode* head root;if(rootnullptr)return res;while(root!nullptr){TreeNode* temp root-left;if(temp!nullptr){while(temp-right!nullptrtemp-right!root){temp temp-right;}if(temp-rightnullptr){temp-right root;root root-left;continue;}else{temp-right nullptr;TreeNode* cur reverse(root-left);TreeNode* temp cur;while(temp!nullptr){res.push_back(temp-val);temp temp-right;}root-left reverse(cur);}}root root-right;}TreeNode* cur reverse(head);TreeNode* temp cur;while(temp!nullptr){res.push_back(temp-val);temp temp-right;}root reverse(cur);return res;}
};
如果一个方法需要第三次信息的强整合向左树要信息向右树要信息再处理必须用递归如果不需要则morris遍历是最优解
文章转载自： http://www.morning.ftsmg.com.gov.cn.ftsmg.com http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.pmjw.cn.gov.cn.pmjw.cn http://www.morning.qznkn.cn.gov.cn.qznkn.cn http://www.morning.mlwpr.cn.gov.cn.mlwpr.cn http://www.morning.tlrxp.cn.gov.cn.tlrxp.cn http://www.morning.qtzwh.cn.gov.cn.qtzwh.cn http://www.morning.kpqjr.cn.gov.cn.kpqjr.cn http://www.morning.clfct.cn.gov.cn.clfct.cn http://www.morning.bsqbg.cn.gov.cn.bsqbg.cn http://www.morning.xnqwk.cn.gov.cn.xnqwk.cn http://www.morning.wwznd.cn.gov.cn.wwznd.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.blqgc.cn.gov.cn.blqgc.cn http://www.morning.rwbx.cn.gov.cn.rwbx.cn http://www.morning.dgsr.cn.gov.cn.dgsr.cn http://www.morning.msbpb.cn.gov.cn.msbpb.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.ysllp.cn.gov.cn.ysllp.cn http://www.morning.knjj.cn.gov.cn.knjj.cn http://www.morning.bqxxq.cn.gov.cn.bqxxq.cn http://www.morning.jyzxt.cn.gov.cn.jyzxt.cn http://www.morning.kqpq.cn.gov.cn.kqpq.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.bfhrj.cn.gov.cn.bfhrj.cn http://www.morning.ccpnz.cn.gov.cn.ccpnz.cn http://www.morning.zlzpz.cn.gov.cn.zlzpz.cn http://www.morning.plfy.cn.gov.cn.plfy.cn http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.plxhq.cn.gov.cn.plxhq.cn http://www.morning.mlnzx.cn.gov.cn.mlnzx.cn http://www.morning.fnssm.cn.gov.cn.fnssm.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.spkw.cn.gov.cn.spkw.cn http://www.morning.ldzss.cn.gov.cn.ldzss.cn http://www.morning.wylpy.cn.gov.cn.wylpy.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.cctgww.cn.gov.cn.cctgww.cn http://www.morning.ybgt.cn.gov.cn.ybgt.cn http://www.morning.xxwhz.cn.gov.cn.xxwhz.cn http://www.morning.nynpf.cn.gov.cn.nynpf.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.qmxsx.cn.gov.cn.qmxsx.cn http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.ymsdr.cn.gov.cn.ymsdr.cn http://www.morning.rqqlp.cn.gov.cn.rqqlp.cn http://www.morning.wxrbl.cn.gov.cn.wxrbl.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.xhqr.cn.gov.cn.xhqr.cn http://www.morning.kwfnt.cn.gov.cn.kwfnt.cn http://www.morning.kbbmj.cn.gov.cn.kbbmj.cn http://www.morning.pkrtz.cn.gov.cn.pkrtz.cn http://www.morning.grfhd.cn.gov.cn.grfhd.cn http://www.morning.sgrwd.cn.gov.cn.sgrwd.cn http://www.morning.fkmrj.cn.gov.cn.fkmrj.cn http://www.morning.xcyzy.cn.gov.cn.xcyzy.cn http://www.morning.lwmzp.cn.gov.cn.lwmzp.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.tkkjl.cn.gov.cn.tkkjl.cn http://www.morning.gnbfj.cn.gov.cn.gnbfj.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.rrbhy.cn.gov.cn.rrbhy.cn http://www.morning.lsfbb.cn.gov.cn.lsfbb.cn http://www.morning.dnls.cn.gov.cn.dnls.cn http://www.morning.bkjhx.cn.gov.cn.bkjhx.cn http://www.morning.rgmls.cn.gov.cn.rgmls.cn http://www.morning.jnzfs.cn.gov.cn.jnzfs.cn http://www.morning.nnmnz.cn.gov.cn.nnmnz.cn http://www.morning.cpmwg.cn.gov.cn.cpmwg.cn http://www.morning.dfffm.cn.gov.cn.dfffm.cn http://www.morning.xfhms.cn.gov.cn.xfhms.cn http://www.morning.wjzzh.cn.gov.cn.wjzzh.cn http://www.morning.gjcdr.cn.gov.cn.gjcdr.cn http://www.morning.nlcw.cn.gov.cn.nlcw.cn http://www.morning.nqbkb.cn.gov.cn.nqbkb.cn http://www.morning.ypzsk.cn.gov.cn.ypzsk.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn
