题解 | #Tree V#

Tree V

http://www.nowcoder.com/practice/e8ee01c28bb24cafb0fc20c524b459ea

题目的主要信息：

已知完全二叉树的DFS正序遍历序列
求所有边两个端点异或的和

方法一：DFS

题目告诉我们这棵树是完全二叉树，根据完全二叉树的性质，对于编号为i的节点，它的左孩子的编号为2i，右孩子的编号为2i+1。因此我们可以根据这个性质，从根节点开始，通过性质得到左右孩子的编号，计算孩子和父节点的异或，再用DFS让左右孩子作为根节点，递归计算。 alt 上图展示了二叉树编号和DFS顺序之间的关系，因为题目给出的数组a是以DFS遍历得到的，现在我们计算端点异或也是用DFS遍历，所以第i个遍历到的端点，权重为a[i]。在DFS实现中，我们需要一个变量count用于保存目前遍历的端点个数。

示例： alt

具体做法：

class Solution {
public:
    static const int MAX=100001;//最多的节点数
    int count=0;
    int w[MAX];//用来保存每个端点的权重
    long long result=0;//用于保存所有边两个端点异或的和
    void dfs(int root,vector<int>& a,int n){
        if(root>n) return;//如果当前节点的编号大于n，则表示root节点不在这棵树上
        w[root]=a[count];//root节点是第count个被遍历的节点，权重在a[count]
        count++;
        if(root!=1){
            result+=w[root]^w[root/2];//计算当前root节点和其父节点之间的异或，并加到result上
        }
        int left=root*2;
        int right=root*2+1;
        dfs(left,a,n);//递归计算左孩子
        dfs(right,a,n);//递归计算右孩子
        
    }
    long long tree5(vector<int>& a) {
        //对数值初始化
        count=0;
        result=0;
        int n=a.size();//总节点数，也是节点最大编号数
        dfs(1,a,n);//从根节点开始遍历
        return result;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，每个节点遍历一次。
空间复杂度： $O (n)$ ，每一个节点都需要记录权重，总共有n个节点。

方法二：自顶向下

对于每一个节点，我们可以考虑它是否有左孩子和右孩子，如果两个孩子都有那么需要进行两次异或。和方法一不同的是，方法二从父节点角度出发，和左右孩子进行异或计算，计算完后，分别在左右子树进行递归。需要注意的是树的边界，即考虑左右子树是否存在。

具体做法：

class Solution {
public:
    long long result=0;
    vector<int> child_count(int size){
        int level=0;
        int l=0,r=0;
        vector<int> res;
        for(int i=0;;i++){//根据完全二叉树的性质计算层数
            if(pow(2,i)<=size&&pow(2,i+1)>size){
                level=i;
                break;
            }
        }
        if(pow(2,level)-1+pow(2,level-1)-1>=size-1){//根据性质计算左右孩子数
            r=pow(2,level-1)-1;//右子树为满二叉树
            l=size-1-r;
        }else{
            l=pow(2,level)-1;//左子树为满二叉树
            r=size-1-l;
        }
        res.push_back(l);
        res.push_back(r);
        return res;
    }
    void traverse(vector<int>& a,int begin,int end){
        int size=end-begin;
        int root=a[begin];
        vector<int> l_r=child_count(size);//得到root节点的左右节点数
        if(l_r[0]!=0){//若左子树不为空
            result+=root^a[begin+1];//root和左孩子的异或
            traverse(a, begin+1, begin+1+l_r[0]);//在左子树上递归进行
        }
        if(l_r[1]!=0){//若右子树不为空
            result+=root^a[begin+1+l_r[0]];//root和右孩子的异或
            traverse(a, begin+1+l_r[0], end);//在右子树上递归进行
        }
    }
    long long tree5(vector<int>& a) {
        result=0;
        int n=a.size();
        traverse(a,0,n);
        return result;
    }
};

复杂度分析：