学步园

来源于

http://blog.csdn.net/bvbook/archive/2008/07/25/2710209.aspx

#include <stack><br /> #include <algorithm><br /> using namespace std;</p> <p>struct Node<br /> {<br /> bool _visited;</p> <p> Node* left;<br /> Node* right;<br /> int maxLeft;<br /> int maxRight;</p> <p> Node()<br /> {<br /> _visited = false;<br /> maxLeft = 0;<br /> maxRight = 0;<br /> left = NULL;<br /> right = NULL;<br /> }<br /> };</p> <p>int maxLen = 0;</p> <p>stack<Node*> nodeStack;</p> <p>void findMaxLen( Node* root )<br /> {<br /> Node* node;</p> <p> if ( root == NULL )<br /> {<br /> return ;<br /> }</p> <p> nodeStack.push( root );<br /> while( !nodeStack.empty())<br /> {<br /> node = nodeStack.top();</p> <p> if ( node->left == NULL && node->right == NULL )<br /> {<br /> nodeStack.pop();<br /> node->_visited = true;<br /> continue;<br /> }<br /> if ( node->left )<br /> {<br /> if ( !node->left->_visited )<br /> {<br /> nodeStack.push( node->left ) ;<br /> }<br /> else<br /> {<br /> node->maxLeft = max( node->left->maxLeft,node->left->maxRight ) + 1;<br /> }<br /> }<br /> if ( ( !node->left || node->left->_visited ) && node->right )<br /> {<br /> if ( !node->right->_visited )<br /> {<br /> nodeStack.push( node->right ) ;<br /> }<br /> else<br /> {<br /> node->maxRight = max( node->right->maxLeft,node->right->maxRight ) + 1;<br /> }<br /> }</p> <p> if (( !node->left || node->left->_visited ) && ( !node->right || node->right->_visited ))<br /> {<br /> maxLen = max( maxLen, node->maxLeft + node->maxRight );<br /> node->_visited = true;<br /> nodeStack.pop();<br /> }<br /> }<br /> }</p> <p>Immediate test case 1：</p> <p>int main()<br /> {<br /> Node *tmp ;<br /> Node* root = new Node();</p> <p> tmp = new Node();<br /> root->left = tmp ;</p> <p> tmp = new Node();<br /> root->right = tmp;</p> <p> tmp = new Node();<br /> root->right->right = tmp;</p> <p> tmp = new Node();<br /> root->right->right->right = tmp;</p> <p> tmp = new Node();<br /> root->right->right->right->left = tmp;<br /> findMaxLen( root );</p> <p> cout << maxLen << endl;<br /> return 0;<br /> }<br />

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bvbook/archive/2008/07/25/2710209.aspx