题解 | NC604 #Tree I#

题目描述

系统中有一棵n个点的完全二叉树，现给出它的BFS层序遍历序列（从根节点开始，自上而下自左到右的一层一层遍历，即首先访问根，然后从左到右访问第2层上的节点，接着是第三层的节点），请你还原这棵树，并返回加密后的答案。
答案加密方法：所有边两个端点异或的和， ，其中(ui, vi))为一条树上的边。
完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。
样例构成的完全二叉树为：

题目分析

因为完全二叉树的特点，n-1层是满二叉树，而第n层是按照从左到右的顺序，因为满二叉树中，非叶子结点都有两个子节点，易知子节点的下标与父节点下标存在两倍的关系，通过对样例分析可以得到以下结论：
当结点 i 满足 2i+1 < n时，说明该结点有左子节点，且左子节点下标为2i+1；
当结点 i 满足 2i+2 < n时，说明该结点有右子节点，且左子节点下标为2i+2；

题目中所示的加密方法主要是遍历树，将所有父节点和子节点的值进行异或相加，即为加密结果。

解题思路

方法1：重构二叉树，递归遍历树
可以根据数组，对完全二叉树进行重构，然后再对这个树进行深度遍历，计算异或和。
重构过程与dfs过程相似，关键是要确定根结点和左右子节点的下标位置：

buildeTree(int[] a, int index){
    TreeNode root = new TreeNode(index);
    root.left = buildTree(a, index*2+1);
    root.right= buildTree(a, index*2+2);
}

方法2：根据完全二叉树的特点，直接遍历数组进行计算
根据上述分析，可以不用构建树，直接根据下标访问结点值，进行异或运算；
根节点和左子节点的异或值：a[i] ^ a[2i+1];
根节点和右子节点的异或值：a[i] ^ a[2i+2];
将所有的异或值加起来，即为结果。

代码实现

方法1：重构二叉树，递归遍历树

// 定义树结构
class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    TreeNode(int val){
        this.val = val;
    }
}
    long res = 0;
    public long tree1 (int[] a) {
        // write code here
        // 构建树
        TreeNode root = buildTree(a, 0);
        // 计算加密异或和
        countSum(root);
        return res;
    }

    public TreeNode buildTree(int[] a, int index){
        if(index >= a.length) return null;
        // 创建根节点
        TreeNode root = new TreeNode(a[index]);
        // 根据完全二叉树的特点，获得根节点的左右子节点
        root.left = buildTree(a, index*2+1);
        root.right = buildTree(a, index*2+2);
        return root;
    }

    public void countSum(TreeNode root){
        if(root == null) return;
        if(root.left != null){
            // 计算根和左子节点的异或和
            res += root.val ^ root.left.val;
        }
        if(root.right != null){
            // 计算根和左子节点的异或和
            res += root.val ^ root.right.val;
        }
        // 递归遍历剩下的结点
        countSum(root.left);
        countSum(root.right);
    }

时间复杂度：，因为构建二叉树和计算异或和的过程都需要遍历整个树，时间花费为2n；
空间复杂度：，在递归过程中，栈的深度最多为n，空间花费为n；

方法2：根据完全二叉树的特点，直接遍历数组进行计算

    public long tree1 (int[] a) {
        // write code here
        long res = 0;
        for(int i=0;2*i+1<a.length;i++){
            // 确定 i 结点的左子节点 2*i+1，获取边的端点异或值
            res += a[i] ^ a[2*i+1];
            if(2*i+2<a.length){
                // 确定 i 结点的右子节点
                res += a[i] ^ a[2*i+2];
            }
        }
        return res;
    }

时间复杂度：，需要遍历一半的数组，时间花费为n/2；
空间复杂度：，需要一个变量来记录计算结果。