问确定二叉树是否对称的思维过程

EN

这是一个可以用光滑递归算法实现的解决方案之一。其思想是首先维护两个指向根的引用，然后将一个子树向左移动，另一个子树向相反的方向移动，然后将两个子树的遍历方向反向，然后指向任一子树上的对称节点(如果存在的话)。

在这里，t1和t2引用左和右子树。

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

这个步骤是检查是否同时存在一个右子树和一个左子树，因为如果我们没有一个子树，那么它就不能是对称的，所以我们返回false。

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

这说明了叶节点，在这些节点中，可以使用null作为左、右子树。因此，我们返回真实；

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 

现在我们知道这两个子树都是有效的(即null)，然后检查它们的值，以检查它们是否相同。如果不一样，我们可以返回假，因为没有必要再看下去。

之所以可以进行比较，是因为我们知道它必须是一个完整的二叉树才能是对称的，所以我们可以将左子树(T1)移到左边的子树(T2)到右边，从而移动右侧子树上的对称节点。

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

isMirror(t1.right, t2.left)后

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

在递归调用isMirror(t1.right, t2.left)之后

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

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

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

它现在执行与上述步骤相同的操作，并展开调用堆栈。

因此，在堆栈帧中，有left表示t1的左子树是否对称于t2的右子树，right表示相反的子树。

因为在递归检查它的子树之前，我们已经检查了t1.val等于t2.val，所以我们知道根是相等的，如果它是相等的，那么返回return left && right，t1的子树是对称的，它是t2的子树。

如果这有点复杂，你可以在帕帕雷上找到它，并检查它可能会使事情变得更清楚。

希望这能有所帮助。

如何证明上述递归版本的正确性？(我想这是有诱惑力的？)

是的，你可以通过归纳来证明这一点。

有人能勾勒出这样一个解决方案的思维过程吗？您是通过实际可视化调用堆栈来验证解决方案，还是有一个很好的高层思维框架来解释这些问题？

我用两种方式解决了这个问题--顺序遍历和递归。通过看到这个问题，我的第一个想法是使用级别顺序遍历。而且，在第一次尝试中考虑次优解(有额外的空间)是没有什么害处的。然后我想出了递归方法。

我觉得这都是练习的问题。您解决的递归问题越多，就越开始在头上思考/可视化相应的递归树。在开始时，我挣扎于它，并使用调试器的帮助来查看函数堆栈在每个调用中的内容。但是调试很耗时，在白板编码中找不到调试的范围。现在，在我的水平上，我可以找出简单的/中的递归问题，在头脑中看到它，通过在钢笔和纸/白板中模拟硬的问题。

这些东西将随着经验和更多的实践而改善。在某些数据结构问题上的经验--看到并解决很多二叉树(指针表示)/BST问题的人，在这里比处理递归的人更有可能表现出色，但没有解决那么多二叉树问题。

希望这能有所帮助！