首页 > 代码库 > 编程之美--3.8

编程之美--3.8

2024-07-08 21:51:12   234人阅读

题目描述：求二叉树节点的最大距离，距离是节点之间边的数目

思路：递归判断左子树右子树以及经过当前节点的值的大小

 1 #include <iostream> 2 #include <queue> 3 #include <climits> 4 #include <algorithm> 5 #include <memory.h> 6 #include <stdio.h> 7 #include <ostream> 8 #include <vector> 9 #include <list>10 #include <cmath>11 #include <string>12 #include <stdexcept>13 #include <stack>14 using namespace std;15 16 struct Node17 {18     Node* leftChild;19     Node* rightChild;20     int val;21     Node():leftChild(NULL),rightChild(NULL)22     {23 24     }25 };26 27 int getTreeheight(Node *root)28 {29     if(root == NULL)30         return 0;31     int left = getTreeheight(root->leftChild)+1;32     int right = getTreeheight(root->rightChild)+1;33     return max(left,right);34 }35 36 int fun(Node *root)37 {38     if(root == NULL)39         return 0;40     int maxlen = getTreeheight(root->leftChild)+getTreeheight(root->rightChild);41     int tmp = max(fun(root->leftChild),fun(root->rightChild));42     return max(maxlen,tmp);43 }44 45 int main()46 {47 48     return 0;49 }

 有个更好的解法：时间和空间都优化了

http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html


联系
我们