愛比的新手筆記

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

 

Example 1:

Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

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. Swapping 2 and 3 makes the BST valid.

 

Constraints:

• The number of nodes in the tree is in the range [2, 1000].
• -231 <= Node.val <= 231 - 1

public class Solution {
        public void RecoverTree(TreeNode root)
        {
            List<int> rslt = new List<int>();
            tree2lst(root, rslt);//先轉成List
            rslt.Sort();//排序
            int i = 0;
            root = lst2tree(root, rslt, ref i);//再依排序的list回寫treeNode
        }

        private void tree2lst(TreeNode node, List<int> rslt)
        {
            if (node == null) return;
            tree2lst(node.left, rslt);
            rslt.Add(node.val);
            tree2lst(node.right, rslt);
        }

        private TreeNode lst2tree(TreeNode node, List<int> rslt, ref int i)
        {
            if (node == null)
                return node;
            lst2tree(node.left, rslt, ref i);
            node.val = rslt[i++];
            lst2tree(node.right, rslt, ref i);
            return node;
        }
}

Taiwan is a country. 臺灣是我的國家