递增顺序查找树【leetcode - 897 - 简单】

野性酷女 2022-03-30 13:46 144阅读 0赞

胡扯：之前吐槽的 leetcode 使用全局变量的问题，应该是我操作的问题。java还是可以使用全局变量的，只要 别在全局变量前面加上 static 就好了。从本题开始，坚持每道题都写一篇简短的文章。

原题位置 ：[https://leetcode-cn.com/problems/increasing-order-search-tree/][https_leetcode-cn.com_problems_increasing-order-search-tree]

## 思路： ##

1、首先把树进行 中序遍历，可以使用 ArrayList 按照中序的顺序存起来。 关于三种遍历查看  [三种遍历][Link 1]

2、然后再去循环数组把一个个结点拼接起来。

3、我最开始没有用 集合，用的是 String 把每一个数字拼接起来，这样后期有个问题就是字符变成数字设计ascii 的问题。其实除了这个还有一个重要的问题，就是如果数字是  222，它会分成三个字符，这明显就错了. 所以使用集合是最好的。

4、在 刷题的时候，  第一步总是来个 非空 判断。

代码一 （击败百分之 20的人）

class Solution {
    
        List<Integer> list = new ArrayList<>();
        void dfs (TreeNode root){
    
            if( root.left != null)
                dfs(root.left);
            list.add(root.val);
            if( root.right != null )
                dfs( root.right );
            return ;
        }
    
        public TreeNode increasingBST(TreeNode root) {
    
    
            if(root == null)
                return root;
    
            dfs(root);
            TreeNode head = new TreeNode( list.get(0) );
            list.remove(0);
            TreeNode head1 = head;
            for(Integer i : list){
                head.left = null;
                TreeNode tem = new TreeNode(i);
                head.right = tem;
                head = tem;
            }
    
            return head1;
        }
    }

代码二（思路和上面的基本一样，简单的优化了一下，打败了 百分之70的人）

class Solution {
        
        TreeNode head = new TreeNode(-1);
        TreeNode head1 = head;
        
        void dfs (TreeNode root){
            
            if( root.left != null)
                dfs(root.left);
            
            head.left = null;
            TreeNode tem = new TreeNode(root.val);
            head.right = tem;
            head = tem;
            
            if( root.right != null )
                dfs( root.right );
            return ;
        }
        
        public TreeNode increasingBST(TreeNode root) {
            
            if(root == null)
                return root;
            dfs(root);                 
            return head1.right;
        }
    }

[https_leetcode-cn.com_problems_increasing-order-search-tree]: https://leetcode-cn.com/problems/increasing-order-search-tree/
[Link 1]: https://blog.csdn.net/Tomwildboar/article/details/85717842