Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
confused what "{1,#,2,3}"
means? >
read more on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1 / \ 2 3 / 4 \ 5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}"
.
中序遍歷,用一個List存儲每個節點的位置,然後雙指針一個從左往右,一個從右往左找到連個錯誤的位置,然後交換連個節點的值。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { List list = new ArrayList<>(); public void recoverTree(TreeNode root) { mid(root); int left = -1; int right = -1; for(int i=0;ilist.get(i+1).val){ left = i; break; } } for(int j=list.size()-1;j>0;j--){ if(list.get(j).val