二叉树恢复

今天刷了一些java基础相关的知识，类加载、线程并发，静态属性与成员加载时机等相关题目，未成体系，刷一道LeetCode作为今天的打卡

https://leetcode.cn/problems/recover-binary-search-tree/description/

题解：

package src;

import java.util.ArrayList;

import java.util.List;

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

class Solution {

    public static void main(String[] args) {

//        TreeNode root = new TreeNode(1);

//        root.left = new TreeNode(3);

//        root.left.right = new TreeNode(2);

        TreeNode root = new TreeNode(3);

        root.left = new TreeNode(1);

        root.right = new TreeNode(4);

        root.right.left = new TreeNode(2);

        Solution solution = new Solution();

        List<TreeNode> treeNodes = solution.recoverTree(root);

        for (int i = 0; i < treeNodes.size(); i++) {

            System.out.println(treeNodes.get(i).val);

        }

    }

    public List<TreeNode> recoverTree(TreeNode root) {

        List<TreeNode> list = new ArrayList<>();

        //正常二叉搜索树中序遍历应该是依次递增的，如果两个树交换位置后就会形成两个拐点，拐点会导致数据走势突然递减,

        // 记录两次递减的坐标位置，交换坐标的值，

        // 若只有一次递减，则交换第一次递减前后node的值

        innerSearch(list, root);

        int index = 0;

        int firstIndex = -1;

        int secondIndex = -1;

        while (index < list.size() - 1) {

            if (list.get(index).val <= list.get(index + 1).val) {

                index++;

                continue;

            }

            if (firstIndex == -1) {

                firstIndex = index++;

                continue;

            }

            secondIndex = index + 1;

            break;

        }

        if (secondIndex == -1) {

            secondIndex = firstIndex + 1;

        }

        int temp = list.get(firstIndex).val;

        list.get(firstIndex).val = list.get(secondIndex).val;

        list.get(secondIndex).val = temp;

        return list;

    }

    private void innerSearch(List<TreeNode> list, TreeNode root) {

        if (root == null) {

            return;

        }

        innerSearch(list, root.left);

        list.add(root);

        innerSearch(list, root.right);

    }

    private static 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;

        }

    }

}

//还可以继续优化一下，在中序遍历的时候就比较记录下Node了，情人节，陪老婆去了

————————————————

版权声明：本文为CSDN博主「张野1994」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_24679971/article/details/129035299