来自一道反转二叉树题目的疑惑(Homebrew 的作者被 Google 拒啦,因为他不会翻转二叉树…)
之前在网上看到:Homebrew 的作者被 Google 拒啦,因为他不会翻转二叉树…
于是自己便去 leetcode 上做下这道题:leetcode-cn.com/problems/invert-bi...
用的是 PHP,下面两种代码
的运行结果却让我产生了疑惑:
function invertTreeMy ($root)
{
if ($root === null) {
return $root;
}
$root->left = $this->invertTree($root->right);
$root->right = $this->invertTree($root->left);
return $root;
}
上面代码运行结果:
function invertTree ($root)
{
if ($root === null) {
return $root;
}
$left = $root->left;
$right = $root->right;
$root->left = $this->invertTree($right);
$root->right = $this->invertTree($left);
return $root;
}
运行结果:
invertTreeMy
跟 invertTree
方法的不同点是:递归调用时,传的变量方式有点不同。
但是输出结果却截然不同,网上搜索了下没发现想要的答案。
希望社区的伙伴大神们能够解答解答
已经明白啦!是我太粗心,没有一步步去推导。 递归前,应该把本次递归的变量先保存起来,不然上一次递归的结果 $root->left会影响到 $root->right