关于不完全二叉树数组表示规则与子节点定位的技术问询

问题1：此类不完全树是否需写出所有缺失节点（末尾除外）？ #

不需要写出所有缺失节点，仅需保留到最后一个非空节点为止的路径上的必要缺失节点。
比如你提到的示例a = [1, NULL, 2, 3]，根节点1的左子节点是NULL，但这个NULL的所有后代都是空节点，且后续非空节点（2、3）属于1的右子树分支，所以1的左子节点的子节点无需写出。只有当某个缺失节点的后续存在非空节点时，这个缺失节点才必须保留，否则会导致后续节点的定位错位。

问题2：正确的子节点定位公式与缺失节点取舍规则 #

子节点定位公式 #

LeetCode的二叉树数组采用0索引，因此：

• 索引为i的节点，左子节点索引为 2*i + 1
• 索引为i的节点，右子节点索引为 2*i + 2

缺失节点取舍规则 #

• 必须保留的NULL：如果某个空节点是通往最后一个非空节点的路径上的节点，必须写出。比如若1的右子节点是NULL，但它的左子节点有非空节点3，数组需写成[1, NULL, NULL, 3]，否则3的索引会错位。
• 可以省略的NULL：如果某个空节点的所有后代都是空节点，且它位于最后一个非空节点之后，就可以省略，无需补全完全二叉树的所有空节点。

中序遍历算法开发提示 #

基于该规则，可通过递归或迭代方式处理数组：

• 递归：对当前索引i，先递归处理左子节点（2*i+1），若该索引在数组范围内且不为NULL则访问；然后访问当前节点；最后递归处理右子节点（2*i+2）。
• 迭代：用栈模拟递归过程，按左-根-右的顺序遍历，遇到NULL则跳过对应分支。

内容的提问来源于stack exchange，提问作者Amazonian