思路篇讲了「遍历」和「分解问题」两种思维方式,本文讲二叉树的构造类问题。
二叉树的构造问题一般都是使用「分解问题」的思路:构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
接下来直接看题。
先来道简单的,这是力扣第 654 题「最大二叉树」,题目如下:
函数签名如下:
每个二叉树节点都可以认为是一棵子树的根节点,对于根节点,首先要做的当然是把想办法把自己先构造出来,然后想办法构造自己的左右子树。
所以,我们要遍历数组把找到最大值 maxVal
,从而把根节点 root
做出来,然后对 maxVal
左边的数组和右边的数组进行递归构建,作为 root
的左右子树。
按照题目给出的例子,输入的数组为 [3,2,1,6,0,5]
,对于整棵树的根节点来说,其实在做这件事:
再详细一点,就是如下伪码:
当前 nums
中的最大值就是根节点,然后根据索引递归调用左右数组构造左右子树即可。
明确了思路,我们可以重新写一个辅助函数 build
,来控制 nums
的索引:
奉上作者的可视化:
东哥带你刷二叉树(构造篇) | labuladong 的算法笔记