欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java/897. Increasing Order Search Tree 递增顺序查找树

程序员文章站 2022-03-16 08:48:07
...

题目

Java/897. Increasing Order Search Tree 递增顺序查找树


Java/897. Increasing Order Search Tree 递增顺序查找树

Java/897. Increasing Order Search Tree 递增顺序查找树

 

代码部分(70ms)

class Solution {
    List<Integer> list = new ArrayList();
    public TreeNode increasingBST(TreeNode root) {
        if(root == null)
            return root;
        changeList(root);
        int len = list.size();
        TreeNode newT = new TreeNode(list.get(0));
        createTree(newT, 1, len);
        return newT;
        
    }
    public void changeList(TreeNode root){
        if(root.left != null)
            changeList(root.left);
        list.add(root.val);
        if(root.right != null)
            changeList(root.right);
    }
    public void createTree(TreeNode root, int n, int len){
        if(n >= len)
            return;
        TreeNode node = new TreeNode(list.get(n));
        n++;
        root.right = node;
        createTree(root.right, n, len);
    }
}

 

  1. 若树为空,返回空树,

  2. 调用 changeList() 将树转换为 list (原理:中序遍历树的过程,将值存入 list ),可得到我们想要的顺序

  3. 按顺序将 list 创建为一个我们想要的树

  4. 返回该树。

 

代码部分二(47ms)

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode node = new TreeNode(0);
        tsp(root,node);
        return node.right;
    }
    public TreeNode tsp(TreeNode root, TreeNode cur){
        if(root == null)
            return cur;
        cur = tsp(root.left, cur);
        cur.right = new TreeNode(root.val);
        cur = cur.right;
        return tsp(root.right, cur);
    }
}
  1. 创建新树的首节点

  2. 调用 tsp()

  3. 若当前节点为空,返回新树的当前节点

  4. 先遍历到最左边的节点(最小的节点),将左节点作为第一个,node.right=根节点,node.right.right = 右节点(若存在)

  5. 不断按左中右的顺序遍历树,并将值赋予新树

  6. 返回 node.right(第一个节点是我们创建的额外节点)

 

代码部分三(一改进,35ms)

class Solution {
    List<Integer> list = new ArrayList();
    public TreeNode increasingBST(TreeNode root) {
        dfs(root);
        TreeNode res = new TreeNode(0);
        TreeNode cur = res;
        for (int node: list) {
            cur.right = new TreeNode(node);
            cur = cur.right;
        }
        return res.right;

    }
    public void dfs(TreeNode node){
        if(node == null)
            return;
        dfs(node.left);
        list.add(node.val);
        dfs(node.right);
    }
}
  1. 调用 dfs() ,中序遍历树并将节点值存入 list

  2. 新建两个节点 res 、cur

  3. 遍历 list ,通过 node 值创建节点,并将其链接到当前节点的右节点,最后将指向当前节点的cur 移到最新节点

  4. 返回 res.right