“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

The title

Given the root node of a binary search tree, root, two nodes in the tree were swapped by mistake. Please restore the tree without changing its structure.

Example 1:

Input: root = [1,3, NULL, NULL,2] Output: [3,1, NULL,null,2] Swap 1 and 3 to make the binary search tree valid.Copy the code

Example 2:

Input: root = [3,1,4, NULL, NULL,2] Output: [2,1,4, NULL, NULL,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swap 2 and 3 to make the binary search tree valid.Copy the code

solution

A binary search tree b binary search tree C binary search tree D binary search tree If we traverse the entire tree, save the result of the traverse, say in an array. So this array should be sorted.

Well, since it’s ordered it’s easy to do, so let’s go through this ordered array. If the array is perfectly ordered, return it. Otherwise, we find two different subscripts I and j, and swap arr[I]. Val and arr[j]. Val.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<TreeNode> list; public void recoverTree(TreeNode root) { list = new ArrayList(); inOrder(root); TreeNode x = null; TreeNode y = null; for (int i = 0; i < list.size() - 1; i++) { if (list.get(i).val > list.get(i+1).val){ y = list.get(i+1); if (x == null) { x = list.get(i); } } } if (x ! = null && y ! = null) { int tmp = x.val; x.val = y.val; y.val = tmp; } } public void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); list.add(root); inOrder(root.right); }}Copy the code

The last

Complexity analysis:

  • Time complexity: O(N), where N is the number of nodes in the binary search tree. The middle-order traversal requires O(N) time, and the two switching nodes are judged to be O(1) in the best case and O(N) in the worst case, so the total time complexity is O(N).

  • Space complexity: O(N). We need an array to store the tree’s mid-order traversal list

Previous articles:

  • Closures are a nice thing to use for data binding
  • Binary tree brush summary: binary tree traversal
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~