二叉树中最大值节电和最小值节点之间的路径

题目描述
有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的节点到权值最小的节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Tree {
public:
    void dfs(TreeNode *p,vector<int>&path,vector<int>&path1,vector<int>&path2,int& ma,int& mi){
        if(p==NULL)
            return;

        if(p->val>ma){
            ma = p->val;
            path1=path;
        }
        if(p->val<mi){
            mi=p->val;
            path2=path;
        }

        path.push_back(0);
        dfs(p->left,path,path1,path2,ma,mi);
        path.pop_back();

        path.push_back(1);
        dfs(p->right,path,path1,path2,ma,mi);
        path.pop_back();
    }
    int getDis(TreeNode* root) {
        // write code here
        int ma=INT_MIN,mi=INT_MAX;
        vector<int>path,path1,path2;
        dfs(root,path,path1,path2,ma,mi);
        int i=0;
        int size1=path1.size(),size2=path2.size();
        while(i<min(size1,size2)&&path1[i]==path2[i])
        {
            i++;
        }

        if(size1<size2){
            return 2*(size1-i)+size2-size1;
        }
        else{
            return 2*(size2-i)+size1-size2;
        }


    }
};