恢复二叉搜索树

迈不过友情╰ 2023-02-23 07:51 77阅读 0赞

### 恢复二叉搜索树 ###

![format_png][]

![format_png 1][]

--------------------

/** * 二叉树类定义 */
    class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode() { 
        }
    
        TreeNode(int val) { 
            this.val = val;
        }
    
        TreeNode(int val, TreeNode left, TreeNode right) { 
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

public class RecoverTree { 
    
        /** * 中序遍历,获得升序序列存到list中 **/
        public static void inorder(TreeNode root, List<Integer> list) { 
            if (root == null){ 
                return;
            }
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    
        /** * 找到中序遍历list序列中被错误调换的两个节点，放到数组中返回 */
        public static int[] findTwoSwapped(List<Integer> list){ 
            int n=list.size();
            int x=-1,y=-1;
            for(int i=0;i<n-1;i++){ 
                if(list.get(i)>list.get(i+1)){ 
                    //第二个错误调换的数
                    y=list.get(i+1);
    
                    //第一个错误调换的数
                    if(x==-1){ 
                        x=list.get(i);
                    }
                }
            }
    
            return new int[]{ x,y};
        }
    
        /** * 递归遍历二叉树，值为x和y的节点相互替换，count为2，用于统计被替换的节点个数，当第二个节点被替换则返回 */
        public static void recoverTree(TreeNode node,int x,int y,int count){ 
            if (node != null) { 
                if(node.val==x||node.val==y){ 
                    node.val=node.val==x?y:x;
                    if(--count==0){ 
                        return;
                    }
                }
    
                recoverTree(node.left,x,y,count);
                recoverTree(node.right,x,y,count);
            }
    
        }
    
        /** * 测试示例 */
        public static void main(String[] args) { 
    
            //构造一个二叉树（上图示例2）
            TreeNode root = new TreeNode(3);
            root.left=new TreeNode(1);
            root.right=new TreeNode(4);
            root.right.left=new TreeNode(2);
    
    
            List<Integer> list=new ArrayList<>();
            inorder(root,list);
            System.out.println("交换前的中序序列"+" " +list.toString());
    
            int[] twoSwapped = findTwoSwapped(list);
            recoverTree(root,twoSwapped[0],twoSwapped[1],2);
    
    
            List<Integer> list2=new ArrayList<>();
            inorder(root,list2);
            System.out.println("交换后的中序序列"+" "+list2.toString());
    
        }
    }

--------------------

输出结果

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdXBlcnpjbC5vc3MtY24tc2hhbmdoYWkuYWxpeXVuY3MuY29tL1BpY0dvLzIwMjAwNzAxMTI1MjQwLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdXBlcnpjbC5vc3MtY24tc2hhbmdoYWkuYWxpeXVuY3MuY29tL1BpY0dvLzIwMjAwNzAxMTI1MzEzLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zdXBlcnpjbC5vc3MtY24tc2hhbmdoYWkuYWxpeXVuY3MuY29tL1BpY0dvLzIwMjAwNzAxMTcwOTQxLnBuZw?x-oss-process=image/format,png