本文共 1022 字,大约阅读时间需要 3 分钟。
题目:给你二叉搜索树的根节点 root ,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗?
解题思路一、对其中序遍历存储其所有结点的值,对其中的值进行遍历,存储器异常值,对树进行遍历,找到异常值,并进行替换。
public void recoverTree(TreeNode root) { Listnums = new ArrayList<>(); inorder(root,nums); // 获取不正确的两个位置 int[] swapped = findTwoSwapped(nums); recover(root,2,swapped[0],swapped[1]); } // 中序遍历获取结果 public void inorder(TreeNode root,List nums) { if(root==null) { return; } inorder(root.left,nums); nums.add(root.val); inorder(root.right,nums); } // 获得中序遍历不确定的两个位置 public int[] findTwoSwapped(List nums) { int n = nums.size(); int x = -1,y=-1;; for(int i=0;i
题解二、中序遍历的隐式遍历过程中寻找其异常值。
// 二叉搜索树的隐式恢复 public void recoverTree_2(TreeNode root) { Stackstack = new Stack<>(); TreeNode x = null, y = null, pred= null; while(!stack.isEmpty()||root!=null) { while(root!=null) { stack.push(root); root = root.left; } root = stack.pop(); if(pred!=null&&root.val
转载地址:http://lwwdf.baihongyu.com/