二叉树（一）高度与深度

高度：从最底层往上数（后序遍历，左右根），更简单（递归）

深度：从上往下数直到有叶子（前序遍历，根左右），较复杂

高度是最大深度

一、求最大深度

 int maxDepth(TreeNode* root) {//递归的终止条件if(root==NULL)return 0;//单层递归逻辑int leftheight=maxDepth(root->left); //左子树高度int rightHeight=maxDepth(root->right); //右子树高度int height=1+max(leftheight,rightHeight); //该树高度return height;}

二、求最小深度

int minDepth(TreeNode* root) {//递归的终止条件if(root==NULL)return 0;//单层递归逻辑int leftHeight=minDepth(root->left); //左子树的最小深度int rightHeight=minDepth(root->right); //右子树的最小深度if(!root->left&&root->right)//若左子树为空，最小深度是右子树深度+1return 1+rightHeight;if(root->left&&!root->right)//若右子树为空，最小深度是左子树深度+1return 1+leftHeight;return 1+min(leftHeight,rightHeight);//左右子树都有，选择最小深度+1}

三、判断是否为平衡二叉树

平衡二叉树：对每个结点来说，左右子树的高度差<=1

int getHeight(TreeNode* root){//递归终止条件if(root==NULL)return 0;//单层递归逻辑int leftHeight=getHeight(root->left);//左子树高度if(leftHeight==-1)return -1; int rightHeight=getHeight(root->right);//右子树高度if(rightHeight==-1)return -1;//如果做右子树高度差大于1，则返回-1（一直直接向上返回-1），否则就继续算高度int result=abs(leftHeight-rightHeight)>1?-1:1+max(leftHeight,rightHeight);return result;}bool isBalanced(TreeNode* root) {if(getHeight(root)==-1)return 0;return 1;}

四、总结

求高度或深度的题目，如果用递归来做，就是用栈（现进后出的思想），先自上而下“压入”进入递归，然后自下而上依次返回“蹦出”。

1、终止条件：

if(root==NULL)

      return 0;

如果是空节点，说明是相对最底层（叶子之下），高度为0，从这里开始return，逐层返回加1

2、单层递归逻辑：

就是按照左右根的顺序，先求出左子树高度，然后求出右子树高度，再求根树的高度或最小深度或判断其他。

（1）求根树高度：返回1+max(leftHeight, rightHeight)

（2）求最小深度：返回1+min(leftHeight, rightHeight)

        注意要先判断左右子树是否为空的情况！

（3）判断是否平衡：

    比较左右子树的高度差

    不平衡时，一直返回-1（很妙）

    平衡时继续返回根树的高度