专业网站建设代理,请人做网站收费多少,网站设置密码怎么破解,昆山建设监察网站高度#xff1a;从最底层往上数#xff08;后序遍历#xff0c;左右根#xff09;#xff0c;更简单#xff08;递归#xff09;
深度#xff1a;从上往下数直到有叶子#xff08;前序遍历#xff0c;根左右#xff09;#xff0c;较复杂
高度是最大深度
一、求…高度从最底层往上数后序遍历左右根更简单递归
深度从上往下数直到有叶子前序遍历根左右较复杂
高度是最大深度
一、求最大深度 int maxDepth(TreeNode* root) {//递归的终止条件if(rootNULL)return 0;//单层递归逻辑int leftheightmaxDepth(root-left); //左子树高度int rightHeightmaxDepth(root-right); //右子树高度int height1max(leftheight,rightHeight); //该树高度return height;}
二、求最小深度
int minDepth(TreeNode* root) {//递归的终止条件if(rootNULL)return 0;//单层递归逻辑int leftHeightminDepth(root-left); //左子树的最小深度int rightHeightminDepth(root-right); //右子树的最小深度if(!root-leftroot-right)//若左子树为空最小深度是右子树深度1return 1rightHeight;if(root-left!root-right)//若右子树为空最小深度是左子树深度1return 1leftHeight;return 1min(leftHeight,rightHeight);//左右子树都有选择最小深度1}
三、判断是否为平衡二叉树
平衡二叉树对每个结点来说左右子树的高度差1
int getHeight(TreeNode* root){//递归终止条件if(rootNULL)return 0;//单层递归逻辑int leftHeightgetHeight(root-left);//左子树高度if(leftHeight-1)return -1; int rightHeightgetHeight(root-right);//右子树高度if(rightHeight-1)return -1;//如果做右子树高度差大于1则返回-1一直直接向上返回-1否则就继续算高度int resultabs(leftHeight-rightHeight)1?-1:1max(leftHeight,rightHeight);return result;}bool isBalanced(TreeNode* root) {if(getHeight(root)-1)return 0;return 1;}
四、总结
求高度或深度的题目如果用递归来做就是用栈现进后出的思想先自上而下“压入”进入递归然后自下而上依次返回“蹦出”。
1、终止条件
if(rootNULL) return 0;
如果是空节点说明是相对最底层叶子之下高度为0从这里开始return逐层返回加1
2、单层递归逻辑
就是按照左右根的顺序先求出左子树高度然后求出右子树高度再求根树的高度或最小深度或判断其他。
1求根树高度返回1max(leftHeight, rightHeight)
2求最小深度返回1min(leftHeight, rightHeight) 注意要先判断左右子树是否为空的情况
3判断是否平衡 比较左右子树的高度差 不平衡时一直返回-1很妙 平衡时继续返回根树的高度
