题解 | #Tree I#_牛客博客

题意整理

给定完全二叉树的层序遍历序列。
还原二叉树，并计算树中所有边的节点间异或值的累加和。

方法一（重建二叉树）

1.解题思路

首先根据层序遍历序列，重建二叉树，找到根节点。
利用重建的二叉树，遍历所有边，将对应异或和累加到结果变量。
返回结果变量res。

2.代码实现

import java.util.*;

//树结构
class TreeNode{
    TreeNode left=null;
    TreeNode right=null;
    int val;
    TreeNode(int val){
        this.val=val;
    }
}

public class Solution {
    /**
     * 
     * @param a int整型一维数组 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    //结果变量
    long res=0;

    public long tree1 (int[] a) {
        //根据a数组，重建二叉树，得到根节点
        TreeNode root=build(a,a.length,1);
        //计算异或和
        xorSum(root);
        return res;
    }

    //重建二叉树
    private TreeNode build(int[] a,int size,int id){
        //递归终止条件
        if(id>size) return null;
        //确定当前节点
        TreeNode root=new TreeNode(a[id-1]);
        //确定左右子树
        root.left=build(a,size,id*2);
        root.right=build(a,size,id*2+1);
        return root;
    }

    //计算异或和
    private void xorSum(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;
        }
        xorSum(root.left);
        xorSum(root.right);
    }
}

3.复杂度分析

时间复杂度：总共有n个节点，所以重建二叉树以及计算异或和时，递归的深度为n，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外深度为n的递归栈，所以空间复杂度为 $O(n)$ 。

方法二（按数组定位左右子节点）

1.解题思路

根据数组访问树中所有节点，由于是完全二叉树，只需访问到最后一个节点的父节点，即可遍历到所有边。所以只需访问到n/2的编号对应的节点。
每次得到当前节点的左右子节点，然后统计异或和。
返回结果变量res。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param a int整型一维数组 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    public long tree1 (int[] a) {
        //初始化结果变量
        long res=0L;
        int n=a.length;
        //根据数组访问树中所有节点
        for(int i=1;2*i<=n;i++){
            //左子节点对应编号
            int l=2*i;
            //右子节点对应编号
            int r=2*i+1;
            //计算异或和
            if(l<=n){
                res+=a[i-1]^a[l-1];
            }
            if(r<=n){
                res+=a[i-1]^a[r-1];
            }
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：循环体需要执行 $n/2$ 次，所以时间复杂度为 $O(n)$ 。
空间复杂度：不需要额外的空间，所以空间复杂度为 $O(1)$ 。