首页 > 代码库 > 编程之美——二叉树中节点间最大距离
编程之美——二叉树中节点间最大距离
关于递归程序：
递归程序结构包括三部分：递归出口、逻辑处理（需要处理的问题）、递归调用（衔接）。
通过递归调用将问题转化为对子问题的解决，通过回溯完成原问题的解答；
递归与数学归纳法：递归是数学归纳法在计算机程序中的体现。使用递归思想设计程序时，我们设置base case，并假设我们会获得n-1的结果，并实现n的结果。这就好像数学归纳法，我们只关注初始和衔接，而不需要关注具体的每一步。
当问题采用递归算法求解时，代码如下：
1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 5 template<class T> 6 class binaryTree 7 { 8 struct node 9 { 10 T elem; 11 node *left; 12 node *right; 13 int nMaxLeft;//左子树最长距离 14 int nMaxRight;//右子树最长距离 15 16 node(const T &x,node *lt=NULL,node *rt=NULL,int nleft=0,int nright=0) 17 :elem(x),left(lt),right(rt),nMaxLeft(nleft),nMaxRight(nright){} 18 ~node(){} 19 }; 20 21 int nmaxLength=0; 22 23 private: 24 node *root; 25 void makeEmpty(node *&t); 26 void findMaxLength(node *&t); 27 public: 28 binaryTree(node *t=NULL) 29 { 30 root=t; 31 } 32 void createBinaryTree(); 33 ~binaryTree() 34 { 35 makeEmpty(root); 36 } 37 int printMaxLenght() 38 { 39 findMaxLength(root); 40 cout<<nmaxLength<<endl; 41 } 42 }; 43 44 template<class T> 45 void binaryTree<T>::createBinaryTree() 46 { 47 queue<node *>que; 48 node *t; 49 T value; 50 51 cout<<"enter root:(-1 represent NULL)"<<":"; 52 cin>>value; 53 54 root=new node(value); 55 que.push(root); 56 57 T ldata,rdata; 58 59 while(!que.empty()) 60 { 61 t=que.front(); 62 que.pop(); 63 64 cout<<"enter left son of the node "<<t->elem<<":"; 65 cin>>ldata; 66 cout<<"enter right son of the node "<<t->elem<<":"; 67 cin>>rdata; 68 69 if(ldata!=-1) 70 que.push(t->left=new node(ldata)); 71 if(rdata!=-1) 72 que.push(t->right=new node(rdata)); 73 } 74 cout<<"construct complement!"<<endl; 75 } 76 77 template<class T> 78 void binaryTree<T>::makeEmpty(node *&t) 79 { 80 if(t->left!=NULL) 81 makeEmpty(t->left); 82 if(t->right!=NULL) 83 makeEmpty(t->right); 84 delete t; 85 } 86 87 template<class T> 88 void binaryTree<T>::findMaxLength(node *&t) 89 { 90 if(t==NULL) 91 return; 92 93 if(t->left!=NULL) 94 findMaxLength(t->left); 95 if(t->right!=NULL) 96 findMaxLength(t->right); 97 98 if(t->left==NULL) 99 t->nMaxLeft=0;100 if(t->right==NULL)101 t->nMaxRight=0;102 103 if(t->left!=NULL)104 {105 int nmax=0;106 nmax=t->left->nMaxLeft>t->left->nMaxRight ? t->left->nMaxLeft : t->left->nMaxRight;107 t->nMaxLeft=nmax+1;108 }109 if(t->right!=NULL)110 {111 int nmax=0;112 nmax=t->right->nMaxLeft>t->right->nMaxRight ? t->right->nMaxLeft : t->right->nMaxRight;113 t->nMaxRight=nmax+1;114 }115 116 if(t->nMaxLeft+t->nMaxRight>nmaxLength)117 nmaxLength=t->nMaxLeft+t->nMaxRight;118 }119 120 int main()121 {122 binaryTree<int>tree;123 tree.createBinaryTree();124 tree.printMaxLenght();125 return 0;126 }
参考：http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html，问题有更好的解法
计算一个二叉树的最大距离有两种情况:
- 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
- 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离；这也就是上面的递归思路；
问题的核心是情况A 及 B 需要不同的信息: A 需要子树的最大深度，B 需要子树的最大距离。只要函数能在一个节点同时计算及传回这两个信息，代码就可以很简单；
代码如下：
1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 5 struct result 6 { 7 int nmaxDistance;//最长距离 8 int nmaxDepth;//最大深度 9 }; 10 11 template<class T> 12 class binaryTree 13 { 14 struct node 15 { 16 T elem; 17 node *left; 18 node *right; 19 20 node(const T &x,node *lt=NULL,node *rt=NULL) 21 :elem(x),left(lt),right(rt){} 22 ~node(){} 23 }; 24 25 private: 26 node *root; 27 void makeEmpty(node *&t); 28 result getMaxDistance(node *&t); 29 public: 30 binaryTree(node *t=NULL) 31 { 32 root=t; 33 } 34 void createBinaryTree(); 35 int printMaxLength() 36 { 37 cout<<getMaxDistance(root).nmaxDistance<<endl; 38 } 39 ~binaryTree() 40 { 41 makeEmpty(root); 42 } 43 }; 44 45 template<class T> 46 void binaryTree<T>::createBinaryTree() 47 { 48 queue<node *>que; 49 node *t; 50 T value; 51 52 cout<<"enter root:(-1 represent NULL)"<<":"; 53 cin>>value; 54 55 root=new node(value); 56 que.push(root); 57 58 T ldata,rdata; 59 60 while(!que.empty()) 61 { 62 t=que.front(); 63 que.pop(); 64 65 cout<<"enter left son of the node "<<t->elem<<":"; 66 cin>>ldata; 67 cout<<"enter right son of the node "<<t->elem<<":"; 68 cin>>rdata; 69 70 if(ldata!=-1) 71 que.push(t->left=new node(ldata)); 72 if(rdata!=-1) 73 que.push(t->right=new node(rdata)); 74 } 75 cout<<"construct complement!"<<endl; 76 } 77 78 template<class T> 79 void binaryTree<T>::makeEmpty(node *&t) 80 { 81 if(t->left!=NULL) 82 makeEmpty(t->left); 83 if(t->right!=NULL) 84 makeEmpty(t->right); 85 delete t; 86 } 87 88 template<class T> 89 result binaryTree<T>::getMaxDistance(node *&t) 90 { 91 if(!t) 92 { 93 result empty={0,-1}; 94 return empty; 95 } 96 97 result lhs=getMaxDistance(t->left); 98 result rhs=getMaxDistance(t->right); 99 100 result maxdistance;101 maxdistance.nmaxDepth=max(lhs.nmaxDepth+1,rhs.nmaxDepth+1);102 maxdistance.nmaxDistance=103 max(max(lhs.nmaxDistance,rhs.nmaxDistance),lhs.nmaxDepth+rhs.nmaxDepth+2);104 return maxdistance;105 }106 107 int main()108 {109 binaryTree<int>tree;110 tree.createBinaryTree();111 tree.printMaxLength();112 return 0;113 }
为了减少 NULL 的条件测试，进入函数时，如果节点为 NULL，会传回一个 empty 变量。empty.nMaxDepth = -1，目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0。
编程之美——二叉树中节点间最大距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。