🐰😺🏚️ 兔猫信奥学院的奇异树庄探秘 🏚️😺🐰

小兔和小猫在信奥学院新发现的奇异树庄中侦查时，惊讶地发现这里的房屋排列正好构成一棵二叉树，入口房屋就是根节点 root。传说这片树庄布满了魔法护罩：

任何一对直接相连的房屋若在同一晚被闯入，就会触发全庄警报。

聪明的小兔决定化身“魔法小偷”，在保证不触动警报的前提下，究竟能盗取到多少金币？每栋房子上都刻有一个非负整数值 val，表示那天能偷到的金币数。只要你偷了某个房子，就不能偷它的父或子，否则警报大作。

输入格式

第一行：整数 n，表示房屋（节点）总数。
第二行：n 个整数 vals[i]，用空格分隔，表示按完全二叉树层序排列的每个节点的偷盗价值。

• 房屋编号按层序 0…n-1，对应数组下标；
• 对于下标 i，
  • 左子房屋在 2·i+1 号（若 < n）；
  • 右子房屋在 2·i+2 号（若 < n）。
• 1 ≤ n ≤ 10⁴
• 0 ≤ vals[i] ≤ 10⁴

输出格式

输出一个整数，表示在不触警报的前提下，一晚能偷到的最高金币总数。

7
3 2 3 0 3 0 1

7

• 树形可视化：

       3
     /   \
    2     3
   / \   / \
  0   3 0   1

• 最优方案：偷 3(root) + 3(左子右孙) + 1(右子右孙) = 7。

7
3 4 5 1 3 0 1

9

• 树形：

       3
     /   \
    4     5
   / \   / \
  1   3 0   1

• 最优偷法：偷 4 + 5 = 9。

🎓 加菲老师寄语：
利用“二叉树打家劫舍”技巧，递归返回「偷」/「不偷」两种状态，你就能瞬间算出在魔法树庄里最安全的偷盗总量！祝探秘成功！