这里给出书中扩展问题提出的非递归解法。就像书中总结的时候给出的叶先生博客中关于本题的解法,这里同样不需要在节点中嵌入nMaxLeft、nMaxRight。
主要原理是基于非递归后续遍历二叉树。额外需要两个栈:一个用于遍历二叉树,另一个用于临时存储以当前节点为根节点的子树的最大深度。当然也可以采取改变结点值来存储最大深度,不过这样虽然简单但并不实用。
遍历二叉树利用辅助栈L_ist的出栈实现,并且每次出栈的时候计算该节点下的最大深度并压入栈L_ist_deep中。这样在计算某节点下的最大深度和最大距离时,该结点有几个孩子不为空L_ist_deep就弹出几次,并将弹出值赋予Left_Data和Righ_Data(这里的左右不是必须对应)然后进行计算。
下面是C++代码请您感受下:
#include <iostream>
#include <stack>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
int Max_Distence_Iterator_New(BinaryTreeNode* Head)
{
if(Head==NULL)
return -1;
int result=0;
BinaryTreeNode* Node;
BinaryTreeNode* Pre=NULL;
stack<BinaryTreeNode*> L_ist;
stack<int> L_ist_deep;
L_ist.push(Head);
while(L_ist.size())
{
Node=L_ist.top();
if(Node->m_pLeft==NULL && Node->m_pRight==NULL)
{
L_ist.pop();
Pre=Node;
L_ist_deep.push(0); //叶子节点的深度为0
}
else if(Pre!=NULL && (Pre==Node->m_pLeft || Pre==Node->m_pRight))
{
//如果有一个子结点为空,则应初始化为-1,以抵消下面计算temp时的+2;
int Left_Data=-1;
int Right_Data=-1;
int temp_value; //当前结点为根节点的子树的最大深度
L_ist.pop();
Pre=Node;
if(Node->m_pLeft && L_ist_deep.size())
{
Left_Data=L_ist_deep.top();
L_ist_deep.pop();
}
if(Node->m_pRight && L_ist_deep.size())
{
Right_Data=L_ist_deep.top();
L_ist_deep.pop();
}
//计算当前结点下的最大深度并入栈
temp_value=((Left_Data>Right_Data ? Left_Data : Right_Data)+1);
L_ist_deep.push(temp_value);
int temp=Left_Data+Right_Data+2;
result=temp>result ? temp : result; //存储临时最大距离
}
else
{
if(Node->m_pRight!=NULL)
L_ist.push(Node->m_pRight);
if(Node->m_pLeft!=NULL)
L_ist.push(Node->m_pLeft);
}
}
return result;
}