Flowsand Cabin

Appearance

翻转二叉树 ​

递归前序遍历的总体思路 ​

翻转的意思是把对称的两个结点（地址）翻转

前序遍历的遍历顺序是 中左右，我们决定在当前结点（假设为 root）遍历到中时，把中结点的左孩子和右孩子翻转

即把翻转左右孩子的代码写到当前结点为中的时候

关于当前结点位置，我学习时是参考了左程云讲解的递归序知识。

如果想搞清楚二叉树递归遍历时，结点是位置在哪里，是怎么运动的。可以观看左程云视频里讲解二叉树递归遍历章节

代码实现 ​

java
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 2. 确定终止条件，当前结点遍历到空就返回
        if (root == null)
            return null;
        // 3. 单层递归逻辑，先翻转，然后递归到下一层。继续翻转
        // 3.1 翻转.此时 root 的位置为 ‘中’ 的位置
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
        // 3.2 递归到下一层
        // root 遍历到中的左孩子
        invertTree(root.left);
        // root 遍历到中的右孩子
        invertTree(root.right);
        return root;
    }
}

两个问题 ​

代码中的两个 return 分别代表什么？ ​

第一个 return ​

我们先搞懂 if (root == null) return null; 这句我们究竟返回什么呢？

在确定终止条件时，我们不仅需要写 if 里的终止条件，我们还要返回一个值。

在本题中只需返回任意一个类型为 TreeNode 的数据，return null 和 return root 都是可行的。（我们暂且标记这个 return 为 return①。）

但为什么可以任意返回呢？

因为 return① 返回的值是返回到 invertTree(root.left); 和 invertTree(root.right); 中的，而这里并没有变量来接收这个返回值。

另外这两句递归语句的作用是把当前结点向下遍历，然后重新执行翻转的操作

第二个 return ​

位置在下面的 return root;中。（我们暂且标记这个 return 为 return②。）

java
invertTree(root.left);
invertTree(root.right);
return root;

这也是最终输出答案的语句，为什么这个就是输出答案呢？

要搞明白这个，我们得弄懂递归中变量的保存，具体到这一题，就是 root 位置的保存。

如下图

Img

每当我们执行一个 invertTree(root.left)，我们会把 root（假设为‘1’）保存到栈里，然后开启一个新的方法栈 invertTree(root) ，里面的 root 是 上一个 root 的左孩子（即 ‘1’ 的左孩子 ‘2’）。

当这个新的方法栈 invertTree(root) 执行完后，我们会返回到旧的 方法栈 invertTree(root.left) 中，然后我们的 root 又变成 ‘1’ 了。

当我们把所有的递归语句执行完，翻转代码也执行完，最后返回的就是根节点 ‘1’，那就是我们要输出的答案-root。

终止条件写 if (root.left == null) return null; 会出现什么？ ​

  • 会有一类测试用例翻转不成功
    • 测试结果:[1,2]，即[1,2,null]
    • 期望结果:[1,null,2]
  • 所以终止条件要写 root == null,让 root 遍历到上面这种用例的 ‘2’ 的位置里，然后执行翻转操作。

关于递归三部曲中 确定返回值的理解。 ​

  • . 递归语句没有接收返回值，只有答案需要返回值，所以我们在方法最后，root 在根节点的时候返回 root，就能返回答案。
    • 终止条件不需要返回值。

Copyright© 2024-present flowsand