后面确定二叉树思想过程是对称的

给定一个二叉树，检查它是否是自身的反射镜（即，围绕其中心对称）。

例如，这个二叉树[1,2,2,3,4,4,3]是对称的：

1 
/\ 
    2 2 
/\/\ 
3 4 4 3

但以下的[1,2,2，空值，如图3所示，空，3]是不是：

来源自：Determine if tree is symmetric

我花了很多时间来解决这个问题，我想出了解决的办法是办出水平序遍历并检查值在每个级别都是回文。这个实现通过了leetcode上的测试。但是，当我阅读社论时，我看到一个非常短暂的递归程序，并且一直困扰着我。

public boolean isSymmetric(TreeNode root) { 
    return isMirror(root, root); } 

public boolean isMirror(TreeNode t1, TreeNode t2) { 
    if (t1 == null && t2 == null) return true; 
    if (t1 == null || t2 == null) return false; 
    return (t1.val == t2.val) 
     && isMirror(t1.right, t2.left) 
     && isMirror(t1.left, t2.right);}

一个如何证明上述递归版本的正确性？（我猜这可以通过归纳来证明吗？）
有人可以概述想出这样的解决方案的思考过程。你是否通过实际可视化调用堆栈来验证解决方案，还是有一个很好的高层思考框架来推断这些问题？

我明白，树是在自身的递归数据结构，即由遵循相同的结构，但由于某种原因，当我尝试验证该解决方案的有效性，左，右子树，我试图想象递归调用最终我的想法变得纠结。 This guy在解释调用堆栈如何展开作为递归进行时做了很好的工作，但我只是想改进我的思维过程以解决这种“简单”的递归问题，因此我在这里发布。

（FWIW，我所熟悉的递归/ DFS /回溯，以及如何呼叫流程，但我还是被卡住上来和验证高层次递归理念，为上述问题）

感谢您的帮助了。

来源

2017-10-13 LinuxGuru-Wannabe

这是一个可以用光滑的递归算法完成的解决方案之一。这个想法是保持两个引用最初指向根，然后将一个子树移到左边，将另一个子树移到相反的方向，反过来，两个孩子现在都已经指向对称节点任何一个子树（如果存在的话）

这里t1和t2指的是左，右子树。

if (t1 == null || t2 == null) return false;

什么这一步确实是检查是否存在既有左，右子树，因为如果我们没有任何一个子树，然后它不能是对称的，因此我们回到false

if (t1 == null && t2 == null) return true;

这个帐户可以将空值作为左右子树使用。所以我们回归真实;

return (t1.val == t2.val) 
     && isMirror(t1.right, t2.left) 
     && isMirror(t1.left, t2.right);}

可以重新写为

if(t1.val != t2.val) return false; 
auto left = isMirror(t1.right, t2.left) 
auto right = isMirror(t1.left, t2.right); 
return left && right

现在我们知道，无论是子树是有效的（即不为空），那么我们检查自己的价值，以检查它们是否相同。如果不相同，我们可以返回假，因为没有进一步观察的意义。

我们可以比较的原因是因为我们知道它必须是一个完全对称的二叉树，我们可以将左子树（t1）移动到左右子树（t2）移动右子树上的对称节点。

后isMirror(t1.right, t2.left)

     1 
        /\ 
       (t2) 2 2(t1) 
        /\/\ 
        4 5 5 4

再次递归

     1 
        /\ 
        2 2 
        /\/\ 
       (t2) 4 5 5 4(t1)

调用isMirror(t1.right, t2.left)后，现在这将反过来调用它的子节点只因为它们都为null返回true。然后检查t1和t2的值，并返回true或false。然后isMirror(t1.left, t2.right)现在被称为到达这里。

它现在与上述步骤相同并展开调用堆栈。

因此，在堆栈帧，我们有left指示如果t1左子树是对称的t2和right右子树指示相反。

既然我们已经检查是否t1.val等于t2.val递归地检查它的孩子之前，我们知道根是平等的，如果它的孩子是平等的，所以我们返回return left && right的t1子树是对称的t2

子树

如果这有点复杂，你可以在papare上找到它，并检查它可能会更好地清理事情。

希望这会有所帮助。

来源

2017-10-13 05:48:14 thebenman

感谢thebenman的调用堆栈可视化。看到解决方案之后，我可以找出它，但它有助于找出一种方法来推断算法的正确性，而无需实际模拟它。在那个方向，你会碰巧知道如何递归版本被证明是正确的？ –

如何证明上述递归版本的正确性？（I 猜测这可以用电感来证明吗？）

是的，你可以通过归纳证明它。

有人可以概述思考过程中提出这样一个解决方案。您是否通过实际可视化调用堆栈来验证解决方案，还是有一个很好的高层思考框架来推理这种问题？

我解决了这个问题的两种方式 - 水平顺序遍历和递归。通过看到这个问题，我的第一个想法是使用级别遍历。在第一次尝试时考虑次优解决方案（有额外的空间）并不令人羞耻。然后我想出了递归方法。

我认为这是关于实践的一切。你解决的递归问题越多，你开始思考/可视化头部相应的递归树就越多。在开始时，我一直在努力，并使用调试器的帮助来查看每次调用中函数堆栈的内容。但是调试非常耗时，并且您无法在白板编码中找到调试范围。现在在我的水平上，我可以通过在纸上/白板上模拟笔头来发现简单/中等递归问题。

这些东西会随着经验和更多练习而改善。具有某些数据结构事务的经验 - 看到并解决大量二叉树（指针表示）/ BST问题的人在这里比在处理递归非常好但未解决二叉树问题的人更有可能胜过许多。

希望这会有所帮助！

来源

2017-10-13 05:49:23

“在第一次尝试时，思考次优解决方案（有额外的空间）没有什么可耻的。”谢谢你的鼓励。您能否勾画出为什么递归算法是正确的归纳证明？ –

后面确定二叉树思想过程是对称的

回答

相关问题