求二叉樹中兩個節點的最遠距離

問題定義

如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。寫一個程序求一棵二叉樹中相距最遠的兩個節點之間的距離。

計算一個二叉樹的最大距離有兩個情況:

• 情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。

• 情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。

思路：

1，后序遍歷每一節點，找出該節點到最右邊的距離以及最左邊的距離；

2，找到之和最大的即可。

//需保存左子樹中最長距離、右子樹最長距離和當前樹的深度。

//以下提供兩種方法。

#include<iostream>
#include<stack>
using namespace std;
int max(int l,int r)
{
	return l>r?l:r;
}
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x)
        :data(x)
        , left(NULL)
        , right(NULL)
    {}
};
class BinaryTree
{
protected:
    BinaryTreeNode* _root;
    BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
    {
        BinaryTreeNode* root = NULL;
        if (index < size&&arr[index] != '#')
        {
            root = new BinaryTreeNode(arr[index]);
            root->left = _CreateBinaryTree(arr, ++index, size);
            root->right = _CreateBinaryTree(arr, ++index, size);
        }
        return root;
    }
     
public:
    BinaryTree()
        :_root(NULL)
    {}
    BinaryTree(int *arr, int size)
    {
        int index = 0;
        _root = _CreateBinaryTree(arr, index, size);
    }
    /*int MaxTwoNodeDistance()
    {
    	if(_root==NULL)
    	{
    		return 0;
		}
		int maxDistance=0;
		_Distance(_root,maxDistance);
		return maxDistance;
	}*/
	int MaxTwoNodeDistance()
	{
		if(_root==NULL)
			return 0;
		int maxLeft=0;
		int maxRight=0;
		return _Distance(_root,maxLeft,maxRight);
	}
    int Height()
    {
        return _Height(_root);
    }
    void PreOrder_Non()
    {
        if (_root == NULL)
            return;
        BinaryTreeNode* cur = _root;
        stack<BinaryTreeNode*> s;
        s.push(_root);
        while (!s.empty())
        {
            cur = s.top();
            printf("%d ", cur->data);
            s.pop();
            if (cur->right)
                s.push(cur->right);
            if (cur->left)
                s.push(cur->left);
        }
        cout << endl;
    }
protected:
	int _Distance(BinaryTreeNode* root,int& left,int &right)
	{
		if(root==NULL)
		{
			left=0;
			right=0;
			return 0;
		}
		int mll,mlr,mrl,mrr,dl,dr;
		if(root->left==NULL)
		{
			left=0;
			dl=0;
		}
		else
		{
			dl=_Distance(root->left,mll,mlr);
			left=max(mll,mlr)+1;
		}
		
		if(root->right==NULL)
		{
			right=0;
			dr=0;
		}
		else
		{
			dr=_Distance(root->right,mrl,mrr);
			right=max(mrl,mrr)+1;
		}
		return max(max(dl,dr),left+right);
	}
	/*int _Distance(BinaryTreeNode* root,int& max)
	{
		if(root==NULL)
			return 0;
		int maxLeft=0;
		int maxRight=0;
		if(root->left)
		{
			maxLeft=_Distance(root->left,max);
			if(maxLeft>max)
				max=maxLeft;
		}
		if(root->right)
		{
			maxRight=_Distance(root->right,max);
			if(maxRight>max)
				max=maxRight;
		}
		if(maxLeft+maxRight>max)
			max=maxLeft+maxRight;
		return maxLeft>maxRight?maxLeft+1:maxRight+1;	
	}*/
    int _Height(BinaryTreeNode* root)
    {
        if (root == NULL)
            return 0;
        int left = _Height(root->left);
        int right = _Height(root->right);
        return left > right ? left + 1 : right + 1;
    }
  
};
int main()
{
	int arr1[]={1,2,4,5,'#','#','#',7,'#','#',3,'#',6};
	int arr2[]={1,2,3,4,'#','#','#',5,'#',6};
	BinaryTree t1(arr1,sizeof(arr1)/sizeof(arr1[0]));
	t1.PreOrder_Non();
	cout<<t1.MaxTwoNodeDistance()<<endl;
	BinaryTree t2(arr2,sizeof(arr2)/sizeof(arr2[0]));
	t2.PreOrder_Non();
	cout<<t2.MaxTwoNodeDistance()<<endl;
}