题目描述

现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度

输入描述:

输入的第一行表示节点的个数n（1 ≤ n ≤ 1000，节点的编号为0到n-1）组成，

下面是n-1行，每行有两个整数，第一个数表示父节点的编号，第二个数表示子节点的编号

输出描述:

输出树的高度，为一个整数

示例1

输入

5

0 1

0 2

1 3

1 4

输出

3
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<cctype>
#include<iostream>
using namespace std;
vector<int> G[1005];
int n;
int dfs(int x){
	if(G[x].size()==0) return 1;
	else if(G[x].size()==1) return 1 + dfs(G[x][0]);
	else return 1 + max(dfs(G[x][0]), dfs(G[x][1]));	
}

int main(){
	
	scanf("%d",&n);
	
	int deg[1005];
	memset(deg,-1,sizeof(deg));
	int u,v;
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		deg[v]=u;
	}
	int root;
	for(int i=0;i<n;i++){
		if(deg[i] == -1){
			root = i;
			break;
		}
	}

	cout<<dfs(root)<<endl;
	return 0;
}

有个缺点，看到什么东西不管是不是重点只要说不通总是爱钻牛角尖。

对于 树的高度和深度（以及结点的高度和深度） 看了几本不同的书，都有各自的说法，多方查证吧，花了很多时间，最后归纳一下。(´｡• ᵕ •｡`) ♡

树的高度和深度


深度定义是从上往下的，高度定义是从下往上的。（其实不用在意这个，反正树的深度高度怎么数都一样的）。

深度和高度涉及到结点的层数，有的教材规定根结点在第0层，有的则规定根结点在第1层。原理都是一样的，因教材而异。

树从根结点开始往下数，叶子结点所在的最大层数称为 树的深度。

有的教材对于树的高度定义是高度就是深度（层数是0123，深度=高度=3；层数是1234，深度=高度=4）；而有的教材树的高度则是看一共有几层。也就是说不论根节点在第几层，树的深度都是和最大层的叶子节点一样。而树的高度只要看有几层就行了（0123是四层，1234也是四层）。
总之在我看来：
有两种说法：

高度就是深度
看层数：

如果根结点第0，层数=深度=高度-1

如果根结点第1，层数=深度=高度

举个栗子_(:3 」∠ )_：
  　




图
左
右




层数
从第0层开始
从第1层开始


最大层数
4
5


深度
4
5


高度（高度=深度）
4
5


高度（数层数）
5
5


补充：
根节点在第0层时候，按照北大数据结构视频的说法就是高度数结点数，深度数路径。从A到G，节点是5层，中间有4段路径，所以深度4，高度5。

其实也可以理解为数高度时候叶子结点从1开始数。因此空数高度0，只有一个根节点高度1。
但是在清华大学 邓俊辉数据结构书中如下：



这本书中可以看出数高度时候叶子结点是从0开始的，因此空数高度-1，只有一个根节点高度0。


结点的高度和深度


结点的深度也是从根结点开始数，是第几层也决定于根结点在第0层还是第1层。根结点的高度则取决于它的子树，该节点子树中最远的那个叶子结点作为1开始数。
例如对于BCD三个点：
B的子树是C和D，数B的高度时候，B的子树中离B最远的叶子节点是G，所以G高度为1，B高度4，D高度3。但是C是叶子节点，C没有真子树，C高度就是1。
  　




图
左
右




BCD高度（叶子节点>=0）
4 1 3
4 1 3


BCD高度（叶子节点>0）
3 0 2
3 0 2


BCD深度
1 2 2
2 3 3



参考书籍和视频课：

《数据结构（C++版） 》 第二版 清华大学出版社 王红梅
《数据结构（C++语言版）》 第三版 清华大学出版社 邓俊辉
《数据结构(用面向对象方法与C++语言描述) 》 第二版 清华大学出版社 殷人昆
《数据结构高分笔记》2019版 机械工业出版社 天勤考研
北京大学 数据结构与算法
华南理工大学 数据结构与算法


(*´ω`)人(´ω`*)我是萝莉安，今天钻牛角尖也成功了呢

树的高度就是数的层数。那怎么计算树的高度呢？我们可以分贝将左节点的高度计算出来和右

节点的高度计算出来，在比较大小。大的就是树的高度。

 

其实不管是求树的高度还是叶子节点个数，都是在遍历整个树，只不过在遍历的过程中满足了某种条件就做出一定的处理，所以树的遍历是最基本的。

typedef struct BiTNode

{

    int data;

    struct BiTNode* lchild, *rchild;

}BiTNode;

int Deepth(BiTNode *root)

{

    int deepthleft = 0;

    int deepthright = 0;

    int deepcount = 0;

    if (root == NULL)

    {

        deepcount = 0;

        return deepcount;

    }

    //求左子树的高度

    deepthleft = Deepth(root->lchild);

    //求右子树的高度

    deepthright = Deepth(root->rchild);

   //每次都要加上根节点的高度

    deepcount = 1+ ((deepthleft > deepthright) ? deepthleft : deepthright);

    return deepcount;

}

void main()

{

    BiTNode t1, t2, t3, t4, t5;

    memset(&t1, 0, sizeof(BiTNode));

    memset(&t2, 0, sizeof(BiTNode));

    memset(&t3, 0, sizeof(BiTNode));

    memset(&t4, 0, sizeof(BiTNode));

    memset(&t5, 0, sizeof(BiTNode));

    t1.data = 1;

    t2.data = 2;

    t3.data = 3;

    t4.data = 4;

    t5.data = 5;

    t1.lchild = &t2;

    t1.rchild = &t3;

    t2.rchild = &t4;

    t3.lchild = &t5;

    int deep=Deepth(&t1);

    printf("deep=%d ", Deepth(&t1));

    system("pause");

}

树的高度
树的高度的递归思想：

根据树的高度的定义，对于任意一个节点来说，树的高度都等于左子树和右子树中比较大的那个 + 该节点高度1之和。

如果节点为空节点，那么高度就为0，因此，树的高度可以利用递归思想求出：
public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

平衡二叉树
那么根据树的高度，由此可以引申出树是否平衡这一概念，也就是平衡二叉树。

平衡二叉树的递归思想：

根据平衡二叉树的定义，一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

想要知道每个节点的左右子树的高度差，首先要知道左右子树的高度。

根据树的高度的递归思想，可以轻松得出左右子树的高度，那么进而判断二者之间的绝对值是否大于1，就可以得出答案。
public boolean isBalanced(TreeNode root) {
        int[] isBalanced = {1};
        isBalanced(root,isBalanced);
        return isBalanced[0] > 0;
    }
    //isBalanced用来判断一棵树是否平衡
    private int isBalanced(TreeNode root,int[] isBalanced) {
        if(root == null)return 0;
        int lh = isBalanced(root.left,isBalanced);//分别求出左右子树的高度，
        int rh = isBalanced(root.right,isBalanced);
        if(Math.abs(lh - rh) > 1)//如果高度差大于1，就说明树不平衡
            isBalanced[0] = -1;
        return Math.max(lh,rh) + 1;
    }

二叉树的直径
二叉树的直径是一个新的概念，我们先来看它的定义：
“一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。”

“注意：两结点之间的路径长度是以它们之间边的数目表示。”
这个定义看起来还是很抽象，我们不容易从中发现他的特性，但是通过举例，我们可以很容易将这一概念和树的高度联系起来。
我们来看下面的例子：
    	  1
         / \
        2   3
       / \     
      4   5    

这棵二叉树的直径长度为3，它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]，我们根据这两个路径的起始节点和结束节点可以发现其实就是以左叶子节点中的一个到右叶子节点中的一个的距离。

那么回头再看定义中"任意两个结点路径长度中的最大值"，就可以发现，树的直径无非就是求树的左子树高度与右子树的高度之和。

根据这一思路，和上面树的高度的递归思想，不难写出如下代码：
public int diameterOfBinaryTree(TreeNode root) {
        int[] res = {0};
        findMaxHeight(root,res);
        return res[0];
    }
    private int findMaxHeight(TreeNode root,int[] res) {
        if(root == null)return 0;
        int lh = findMaxHeight( root.left, res);
        int rh = findMaxHeight( root.right, res);
        res[0] = Math.max(res[0],lh + rh);
        return Math.max(lh,rh) + 1;
    }

树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/
树的最小深度就是根节点到叶子节点的最小距离，和树的最大深度正好相反，所以根据文章开头的树的最大深度的代码来讲，只需要将最后的返回条件改为Math.min(left,right)即可。
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        //下面这行代码的出现是因为如果有了左右子树其中一个为空时，最短深度就为另外一个不为空的树（根据题意的设定）
        if(left == 0 || right == 0) return left + right + 1;
        return Math.min(left,right) + 1;
    }
}

另外一种递归解法
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)return 0;
        int[] res = {Integer.MAX_VALUE};
        minDepth(root,res,1);
        return res[0];
    }
    private void minDepth(TreeNode node,int[] res,int cur_Dep) {
        if(node.left == null && node.right == null) {
            res[0] = Math.min(res[0],cur_Dep);
            return;
        }
        if(cur_Dep >= res[0])return;
        if(node.left != null) minDepth(node.left,res,cur_Dep + 1);
        if(node.right != null) minDepth(node.right,res,cur_Dep + 1);        
    }
}

总结
无论是平衡树的概念，还是二叉树的直径的概念。其实核心概念都是树的高度。