百度站长工具网站b2b采购平台

恢复二叉搜索树

题目描述

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例1

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

示例2

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

题解

因为二叉搜索树的性质可得，将其中序遍历存储到列表中，数值为单调递增，由此可以得到以下步骤

• 遍历列表，找到递增中断点
• 再次遍历列表，找到中断点应该在的位置
• 将两个数值进行交换

完成之后即为所求

想法代码

public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null){this.val = val;this.left = left;this.right = right;}
}
class Solution
{IList<TreeNode> travelList = new List<TreeNode>();public static void Main(String[] args){TreeNode root = new TreeNode(3){left = new TreeNode(1),right = new TreeNode(4){left = new TreeNode(2)}};Solution solution = new Solution();solution.RecoverTree(root);foreach (var a in solution.travelList){Console.Write(a.val + " ");}}public void RecoverTree(TreeNode root){Travel(root);int index1 = 1;int index2 = 0;while (index1 < travelList.Count){if (travelList[index1].val > travelList[index1 - 1].val){index1++;}else{break;}}while (index2 < travelList.Count){if (travelList[index2].val > travelList[index1 - 1].val){break;}index2++;}TreeNode treeNode1 = travelList[index1 - 1];TreeNode treeNode2 = travelList[index2 - 1];int val1 = treeNode1.val;int val2 = treeNode2.val;treeNode1.val = val2;treeNode2.val = val1;}public void Travel(TreeNode root){if (root == null){return;}Travel(root.left);travelList.Add(root);Travel(root.right);}
}
avel(root.left);travelList.Add(root);Travel(root.right);}
}