料金

二分探索木のリートコードを回復する



Recover Binary Search Tree Leetcode



二分探索木（BST）の2つの要素が誤って交換されています。

再帰的方法

思想

この質問は、2つの要素が正しく交換されていないバイナリ検索ツリーを復元するために必要です。順序はBSTによってトラバースされ、逆の順序で検出されます。考慮すべき2つの状況があります。



  1. 位置がずれている2つのノードは、隣接する親子ツリーの関係であり、1次トラバーサル逆順で最初のノードを見つけます。

  2. 置き忘れた2つのノードは、親子関係ではありません。これは、2つの逆順が発生する場合です。その場合、この時点で交換する必要のある要素は、最初の逆順の前の要素と2番目の逆順の後の要素である必要があります。



複雑さ

時間O（n）スペーススタックO（logn）

コード

TreeNode pre, first, second public void recoverTree(TreeNode root) { pre = null first = null second = null inorder(root) if (first != null && second != null){ Int tem = first.val / / only change val is not node first.val = second.val second.val = tem } } private void inorder(TreeNode root){ if (root == null){ return } inorder(root.left) if (pre == null){ Pre = root / / initialization pre } else { if (pre.val > root.val){ if (first == null){ First = pre//first reverse order } Second = root / / If the first time to find the nearest neighbor, if not adjacent, then find the second reverse order after the traversal } Pre = root / / assign pre } inorder(root.right) }