不平衡(或非堆)二叉树可以使用数组表示,如下所示:
array = [1, 2, null, 3, 4, 5, 6, null, 7, 8, null]
1
/ \
2 null
/ \
3 4
/ \ / \
5 6 null 7
/ \
8 null
如何使用给定的数组进行树遍历?更具体地说,如何计算父母左右孩子的指数?
在平衡树(例如堆树)中,我们可以使用父级索引轻松计算两个子级索引,反之亦然,如下所示。
leftChildIdx = 2 * parentIdx + 1
rightChildIdx = 2 * parentIdx + 2
有没有一种简单的方法可以使用数组遍历这个不平衡的或看似随机的二叉树?