Why do they have to have brains? Is it impossible that another structure could serve a similar purpose? Like, how long did it take us to figure out what brains are for?
They don't need to have "brains" in the sense that humans do, ie. discrete neurons and axons, but they do need to have "neural networks" - networks of nonlinear operators with a training mechanism. I'm aware of zero evidence that trees perform computation on a larger-than-single-cell basis.
You cannot direct growth at the scale of a single cell. There are many computations (based on hormonal gradients and other mechanisms) that occur at the scale of larger structures, such as leaves or branches. Of course, those mechanicisms are not going to create consciousness.