algorithm - 判断二叉树是否对称背后的思考过程

Question

问题描述如下:

给定一棵二叉树，检查它是否是自身的镜像(即围绕其中心对称)。

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

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

但是下面的 [1,2,2,null,3,null,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);}

1. 如何证明上述递归版本的正确性？ (我想这可以归纳证明？)
2. 有人可以概述提出这样一个解决方案的思维过程吗？您是通过实际可视化调用堆栈来验证解决方案，还是有一个很好的高级思维框架来推理此类问题？

我知道树本身是一种递归数据结构，即由遵循相同结构的左子树和右子树组成，但出于某种原因，当我尝试验证此解决方案的有效性时，我尝试可视化递归调用并最终可视化我的思想纠缠不清。 This guy在解释调用堆栈如何随着递归进行展开方面做得很好，但我只是想改进我对这种“简单”递归问题的思考过程，因此我在这里发帖。

(FWIW，我熟悉递归/DFS/回溯以及调用流程是如何进行的，但我仍然无法提出并验证上述问题的高级递归想法)

感谢您的帮助。

Answer 1

这是可以使用巧妙的递归算法完成的解决方案之一。这个想法是保持两个引用最初指向根，然后将一个子树向左移动，另一个子树向相反的方向移动，并且反转两个 child 的遍历方向，然后指向对称节点任一子树(如果存在)

这里的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 

现在我们知道两个子树都是有效的(即不为空)，然后我们检查它们的值以检查它们是否相同。如果不相同，我们可以返回 false，因为进一步查找没有意义。

我们之所以可以比较是因为我们知道它必须是完全二叉树才能对称我们可以将左子树(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)

现在这将依次调用它的子节点只返回真，因为它们都是空的。然后检查 t1 和 t2 的值并返回 true 或 false。然后现在调用 isMirror(t1.left, t2.right) 到达这里。

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

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

所以在堆栈帧中我们有 left 指示 t1 的左子树是否与 t2 的右子树对称并且 right 表示相反。

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

如果这有点令人费解，您可以在纸上追踪它并检查它可能会更好地解决问题。

希望这对您有所帮助。