一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 901|回复: 2
收起左侧

[算法题] 小白请教Compute tree height计算树的高度

[复制链接] |试试Instant~ |关注本帖
回帖奖励 2 根萝卜 回复本帖可获得 1 根萝卜奖励! 每人限 1 次(中奖概率 50%)
desperatelife 发表于 2016-4-19 03:22:54 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
You are given a description of a rooted tree. Your task is to compute and output its height. Recall
that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a
leaf to the root. You are given an arbitrary tree, not necessarily a binary tree.
简单来说就是数组对应的下标就是自己的子节点,如果是-1的话,对应的下标就是根;
Input:
5
4 -1 4 1 1
Output:
3
Explanation:
The input means that there are 5 nodes with numbers from 0 to 4, node 0 is a child of node 4, node
1 is the root, node 2 is a child of node 4, node 3 is a child of node 1 and node 4 is a child of node 1.
The height of this tree is 3, because the number of vertices on the path from root 1 to leaf 2 is 3.
树的结构如下
       1
     /   \
    3    4

       /    \
      0      2  
http://www.geeksforgeeks.org/fin ... ented-parent-array/  Amazon貌似考过
跟这道题其实是一道题,但是这个树不一定只是二叉树。
这道题有很多种做法,可以不用转化成树也可以直接求解。
  1. class BinaryTree {

  2.     // This function fills depth of i'th element in parent[].  The depth is
  3.     // filled in depth[i].
  4.     void fillDepth(int parent[], int i, int depth[]) {

  5.         // If depth[i] is already filled
  6.         if (depth[i] != 0) {
  7.             return;
  8.         }

  9.         // If node at index i is root
  10.         if (parent[i] == -1) {
  11.             depth[i] = 1;
  12.             return;
  13.         }

  14.         // If depth of parent is not evaluated before, then evaluate
  15.         // depth of parent first
  16.         if (depth[parent[i]] == 0) {
  17.             fillDepth(parent, parent[i], depth);
  18.         }

  19.         // Depth of this node is depth of parent plus 1
  20.         depth[i] = depth[parent[i]] + 1;
  21.     }

  22.     // This function returns height of binary tree represented by
  23.     // parent array
  24.     int findHeight(int parent[], int n) {
  25.          
  26.         // Create an array to store depth of all nodes/ and
  27.         // initialize depth of every node as 0 (an invalid
  28.         // value). Depth of root is 1
  29.         int depth[] = new int[n];
  30.         for (int i = 0; i < n; i++) {
  31.             depth[i] = 0;
  32.         }

  33.         // fill depth of all nodes
  34.         for (int i = 0; i < n; i++) {
  35.             fillDepth(parent, i, depth);
  36.         }

  37.         // The height of binary tree is maximum of all depths.
  38.         // Find the maximum value in depth[] and assign it to ht.
  39.         int ht = depth[0];
  40.         for (int i = 1; i < n; i++) {
  41.             if (ht < depth[i]) {
  42.                 ht = depth[i];
  43.             }
  44.         }
  45.         return ht;
  46.     }

  47.     // Driver program to test above functions
  48.     public static void main(String args[]) {

  49.         BinaryTree tree = new BinaryTree();

  50.         // int parent[] = {1, 5, 5, 2, 2, -1, 3};
  51.         int parent[] = new int[]{-1, 0, 0, 1, 1, 3, 5};

  52.         int n = parent.length;
  53.         System.out.println("Height is  " + tree.findHeight(parent, n));
  54.     }
  55. }
复制代码
但是现在如果想用树的方法如何做呢? 构建树的结构的时候,是不是需要用一个hashmap把数字和对应的树节点联系起来,才方便调用树节点?
还有应该怎么计算二叉树的高度呢,递归,DFS,BFS,具体如何实现呢?非常感谢!!!!


ykwwind 发表于 2016-4-19 03:32:01 | 显示全部楼层
本帖最后由 ykwwind 于 2016-4-19 03:37 编辑

构建树的结构...就是构建图啊.
一个List<List<Integer>> graph;
一个boolean[] isVisted;

Recursion: height(root) =  Math.max(height(root.left), height(root.right)+1;
DFS: dfs(root), 走一遍维护一个max;
BFS: layer by layer search....最后一个layer的层数就是height......
没有胡萝卜......ToT
回复 支持 反对

使用道具 举报

luochen01 发表于 2016-4-20 21:52:27 | 显示全部楼层
2叉树根n叉树没区别啊,递归的话直接max (child.height) +1就行了。。。
聪哥,求胡萝卜

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 00:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表