求二叉树中最远的两个节点的距离

爱被打了一巴掌 2022-07-14 02:11 188阅读 0赞

**求二叉树中最远的两个节点的距离**

短短的代码中其实涉及到了三道题目：

1.  **利用已知序列递归的建一棵二叉树**
2.  **递归的求一棵树的深度**
3.  求二叉树中距离最远的两个节点的距离
4.  利用类似的思想判断一棵树是否为平衡二叉树；
    
    ：利用递归求树的深度的思想，在其中加入一个最大距离的引用的参数，利用了引用参数的特性，即可求得最大距离，比较简单，下面列出代码及图示；

给出两组测试用例的图示：

![这里写图片描述][20161123194822492]

//代码实现

#include<iostream>
    
    using namespace std;
    
    //先建一颗二叉树
    struct Node
    {
        int _data;
        Node* _left;
        Node* _right;
    
        Node(const int& data):_data(data),_left(NULL),_right(NULL){}
    };
    
    class BinaryTree
    {
        Node* _root;
    public:
        BinaryTree(int* arr,size_t size)
        {
            int index = 0;
            _root = _GreatTree(arr,size,'#',index);
        }
    
    
        //前序递归建树
        Node* _GreatTree(int* arr, size_t size,int invalid, int& index)
        {
            Node* root = NULL;
            if(index < size && arr[index] != invalid)
            {
                root = new Node(arr[index]);
                root->_left = _GreatTree(arr,size,invalid,++index);
                root->_right = _GreatTree(arr,size,invalid,++index);
            }
            return root;
        }
    
        //求二叉树最远两个节点的距离
        void MaxDistant()
        {
            //利用递归不断的往回带
            int maxlenth = 0;//最远距离
    
            //顺带求了一下树的深度
            cout<<_MaxDistance(_root,maxlenth)<<endl;
    
            //最后比较到根节点，输出最远距离
            cout<<maxlenth<<endl;
        }
    
        //扩展,我们在判断一棵树是否是平衡二叉树的时候同样是利用这种思想；
        bool IsBlance()
        {
            int heigh = 0;
            //方式一
            //return _IsBanlanceOne(_root);
    
            //方式二
            return _IsBanlanceTwo(_root,heigh);
        }
    
    protected://保护实现细节
    
    
        //方式一  每个节点遍历多次，效率低
        bool _IsBanlanceOne(Node* root)
        {
            if(root == NULL)
                return true;
    
            int leftDepth = _IsBanlanceOne(root->_left);
            int rightDepth = _IsBanlanceOne(root->_right);
            int distance = leftDepth - rightDepth;
    
            if(distance > 1 || distance < -1)
                return false;
    
            return _IsBanlanceOne(root->_left) && _IsBanlanceOne(root->_right);
        }
    
        //方式二   后序遍历的方式，边遍历边判断
        bool _IsBanlanceTwo(Node* root, int& heigh)
        {
            if(root == NULL)
                return true;
    
            //当然，为了看起来好理解一些，我把返回值的情况都单独列出来
            //最好是把情况合并起来，减少返回值
    
            int leftheigh = heigh;
            if( _IsBanlanceTwo (root->_left , leftheigh) == false )
                return false;
    
            int rightheigh = heigh;
            if( _IsBanlanceTwo (root->_right , rightheigh) == false)
                return false;
    
            heigh = leftheigh > rightheigh ? leftheigh+1 : rightheigh+1;
    
            return abs(rightheigh - leftheigh) < 2;
        }
    
        int _MaxDistance(Node* root, int& maxlenth)
        {
            if(root == NULL)
                return 0;//表示到了叶子节点
    
            int leftDepth = _MaxDistance(root->_left,maxlenth);//左子树深度
            int rightDepth = _MaxDistance(root->_right,maxlenth);//右子树深度
    
            //判断当前子树的左右深度是否比最远距离lenth大，大则替换；
            int tmp = leftDepth+rightDepth;
            if(tmp > maxlenth)
                maxlenth = tmp;
    
            //当前节点的深度即左右子树最大的深度的基础上+1；
            return leftDepth > rightDepth ? leftDepth+1:rightDepth+1;
        }
    };
    
    
    
    
    int main()
    {
        //根据给出的序列建一颗二叉树，其中'#'代表非法值。即用来表示NULL；
        //给出两组测试数据
        //int array[15] = {1,2,'#',1,3,'#','#',4,5,'#',6,'#',7,'#','#',8};
        int array[15] = {
       1,2,1,3,'#','#',4,5,'#',6,'#',7,'#','#',8};
        BinaryTree b(array,15);
    
        b.MaxDistant();
        system("pause");
        return 0;
    }

[20161123194822492]: /images/20220714/0825ace832234a519f587c56e9a2310a.png