[每日一道小算法（十一）][二叉树] 现在给定这棵树上所有的父子关系，求这棵树的高度

心已赠人 2023-07-02 08:25 34阅读 0赞

前言：  
二叉树是一个高频考点，所以今天来分享一道二叉树求高度的问题。

### 概念 ###

在进行解题之前我们先看一下，什么是二叉树？  
二叉树是树形结构的一种重要类型，在实际应用中具有十分重要的意义。  
二叉树是n个结点的有限集合，每个结点至多只有两棵子树。他或是空集，或是由一个根节点及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。

### 二叉树的高度和深度 ###

高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。  
深度：从根节点到该节点的最长简单路径边的条数。  
高度：从该节点到叶子节点的最长简单路径边的条数。  
所以树的深度和高度是相等的，而对于其他结点来说深度和高度不一定相等。  
![在这里插入图片描述][20200128124212476.png]  
如上图所示：  
B、C的节点深度都为1，因为从根节点到该节点的边数为1，B的高度为2，而C的高度为1。

### 题目描述 ###

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

输入描述：

输入的第一行表示节点的个数n（1 ≤ n ≤ 1000，节点的
    编号为0到n-1）组成，下面是n-1行，每行有两个整数，
    第一个数表示父节点的编号，第二个数表示子节点的编号

示例：

5
    0 1
    0 2
    1 3
    1 4

输出：

### 解题思路 ###

求树的高度，就是求层数最大的结点的层数。在划分一下其实就是子节点的层数等于父节点层数加一。  
我们可以用一个length为节点数目n的数组来维护各节点的层数此节点的值作为数组下标，此节点的层数作为数组的值。

### 代码样例 ###

package com.asong.leetcode.TreeTest;
    
    
    import java.util.Scanner;
    
    public class Solution { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int num = scanner.nextInt();
            if(num<3)
            { 
                System.out.println(num);
            }else
            { 
                int[] height = new int[num];
                int[] binary = new int[num];
                //init height 1
                int max = 0 ;
                height[0] = 1;
                for (int i = 0; i < num-1 ; i++) { 
                    int parent = scanner.nextInt();
                    int child = scanner.nextInt();
                    //保存父结点
                    binary[parent] +=1;
                    if(binary[parent]<3)
                    { 
                        height[child] = height[parent]+1;
                    }
                    max = Math.max(max,height[child]);
                }
                System.out.println(max);
            }
        }
    }

[20200128124212476.png]: https://img-blog.csdnimg.cn/20200128124212476.png