乐趣区

关于后端:面试高频题二叉树神级遍历入门

jiezi

题目形容

这是 LeetCode 上的 99. 复原二叉搜寻树 ，难度为 中等。

Tag :「二叉树」、「树的搜寻」、「递归」、「迭代」、「中序遍历」、「Morris 遍历」

给你二叉搜寻树的根节点 root，该树中的 恰好 两个节点的值被谬误地替换。请在不扭转其构造的状况下，复原这棵树。

示例 1：

输出：root = [1,3,null,null,2]

输入：[3,1,null,null,2]

解释：3 不能是 1 的左孩子，因为 3 > 1。替换 1 和 3 使二叉搜寻树无效。

示例 2：

输出：root = [3,1,4,null,null,2]

输入：[2,1,4,null,null,3]

解释：2 不能在 3 的右子树中，因为 2 < 3。替换 2 和 3 使二叉搜寻树无效。

提醒：

  • 树上节点的数目在范畴 $[2, 1000]$ 内
  • $-2^{31} <= Node.val <= 2^{31} – 1$

进阶：应用 $O(n)$ 空间复杂度的解法很容易实现。你能想出一个只应用 $O(1)$ 空间的解决方案吗？

根本剖析

首先，别想简单了。

所谓的复原二叉树（两节点调换），只须要将两节点的 val 进行调换即可，而不须要对节点自身进行调换。

中序遍历 – 递归 & 迭代

二叉搜寻树，其中序遍历是有序的。

要找到哪两个节点被调换，可通过比对中序遍历序列来实现。

但将整个中序遍历序列保留下来，再检测序列有序性的做法，复杂度是 $O(n)$ 的（不要说题目要求的 $O(1)$，连 $O(h)$ 都达不到）。

所以第一步，这个「递归 & 迭代」的次优解，咱们先思考如何做到 $O(h)$ 的空间复杂度，即在中序遍历过程中找到调换节点。

其实也很简略，除了应用 a 和 b 来记录调换节点，额定应用变量 last 来记录以后遍历过程中的前一节点即可：

若存在前一节点 last 存在，而且满足前一节点值大于以后节点（last.val > root.val），违反“有序性”，依据是否为首次呈现该状况分状况探讨：

  • 若是首次满足条件，即 a == null，此时上一节点 last 必然是两个调换节点之一，而以后 root 只能说是待定，因为有可能是 last 和 root 实现调换，也有可能是 last 和后续的某个节点实现调换。

    此时有 a = last, b = root

  • 若是非首次满足条件，即 a != null，此时以后节点 root 必然是两个调换节点中的另外一个。

    此时有 b = root

综上：如果整个中序遍历的序列中“逆序对”为一对，那么调换节点为该“逆序对”的两个成员；若“逆序对”数量为两对，则调换节点为「第一对“逆序对”的首个节点」和「第二对“逆序对”的第二个节点」。

Java 代码（递归）：

class Solution {
    TreeNode a = null, b = null, last = null;
    public void recoverTree(TreeNode root) {dfs(root);
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
    void dfs(TreeNode root) {if (root == null) return ;
        dfs(root.left);
        if (last != null && last.val > root.val) {if (a == null) {a = last; b = root;} else {b = root;}
        }
        last = root;
        dfs(root.right);
    }
}

Java 代码（迭代）：

class Solution {public void recoverTree(TreeNode root) {Deque<TreeNode> d = new ArrayDeque<>();
        TreeNode a = null, b = null, last = null;
        while (root != null || !d.isEmpty()) {while (root != null) {d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (last != null && last.val > root.val) {if (a == null) {a = last; b = root;} else {b = root;}
            }
            last = root;
            root = root.right;
        }
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
}
  • 工夫复杂度：$O(n)$
  • 空间复杂度：$O(h)$，其中 $h$ 为树高

中序遍历 – Morris 遍历

Morris 遍历也就是常常说到的“神级遍历”，其本质是通过做大常数来升高空间复杂度。

还是以二叉树的中序遍历为例，无论是递归或是迭代，为了在遍历完左节点（也能够是左子树）时，仍能回到父节点，咱们须要应用数据结构栈，只不过在递归做法中是用函数调用充当栈，而在迭代做法则是显式栈。

这使得空间复杂度为 $O(h)$，而 Morris 遍历的外围则是利用“门路底部节点”中的闲暇指针进行线索。

举个 🌰，对于一棵最简略的二叉树：

在中序遍历过程中，如果抉择递归或迭代形式，并且不应用栈的状况，当遍历完左子节点（或左子树的最初一个节点）后，将会面临无奈返回根节点的问题。

在 Morris 遍历中，从根节点开始，尚未真正遍历左子节点之前，就会先建设「左子节点（或左子树的最初一个节点）」与「以后根节点」之间的链接，从而防止应用栈。

具体的，Morris 遍历的中序遍历遵循如下流程（喜爱的话能够背过）：

  1. 令根节点为以后节点

  2. 只有以后节点不为空（while (root != null) ），反复执行如下流程：

    • 若以后节点的左子节点为空（root.left = null），将以后节点更新为其右子节点（root = root.right)

    • 若以后节点的左子节点不为空，利用长期变量 t 存储，找到以后节点的前驱节点（左子树中最初一个节点）：

      • 若前驱节点的右子节点为空（t.right = null），将前驱节点的右子节点链接到以后节点（t.right = root），并将以后节点更新为左子节点（root = root.left）
      • 若前驱节点的右子节点不为空，阐明已链接到以后节点，此时将前驱节点的右子节点置空（删除链接 t.right = null），遍历以后节点，并将以后节点更新为右子节点（root = root.right）

Java 代码：

class Solution {public void recoverTree(TreeNode root) {
        TreeNode a = null, b = null, last = null;
        while (root != null) {if (root.left == null) {if (last != null && last.val > root.val) {if (a == null) {a = last; b = root;} else {b = root;}
                }
                last = root;
                root = root.right;
            } else {
                TreeNode t = root.left;
                while (t.right != null && t.right != root) t = t.right;
                if (t.right == null) { // 若前驱节点右子树为空, 阐明是真正遍历左子树前, 建设与以后根节点的链接, 而后开始真正遍历左子树
                    t.right = root;
                    root = root.left;
                } else {  // 若已存在链接, 阐明是第二次拜访根节点, 左子树（前驱节点）已遍历完, 此时应该解开链接, 遍历以后节点以及右子树
                    t.right = null;
                    if (last != null && last.val > root.val) {if (a == null) {a = last; b = root;} else {b = root;}
                    }
                    last = root;
                    root = root.right;
                }
            }
        }
        int val = a.val;
        a.val = b.val;
        b.val = val;
    }
}
  • 工夫复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.99 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

退出移动版