专业网站制作哪家专业百度浏览器广告怎么投放
恢复二叉搜索树
难度：中等
题目描述
给你二叉搜索树的根节点 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);}
}