Java/897. Increasing Order Search Tree 递增顺序查找树
程序员文章站
2022-03-16 08:48:07
...
题目
代码部分(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);
}
}
-
若树为空,返回空树,
-
调用 changeList() 将树转换为 list (原理:中序遍历树的过程,将值存入 list ),可得到我们想要的顺序
-
按顺序将 list 创建为一个我们想要的树
-
返回该树。
代码部分二(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);
}
}
-
创建新树的首节点
-
调用 tsp()
-
若当前节点为空,返回新树的当前节点
-
先遍历到最左边的节点(最小的节点),将左节点作为第一个,node.right=根节点,node.right.right = 右节点(若存在)
-
不断按左中右的顺序遍历树,并将值赋予新树
-
返回 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);
}
}
-
调用 dfs() ,中序遍历树并将节点值存入 list
-
新建两个节点 res 、cur
-
遍历 list ,通过 node 值创建节点,并将其链接到当前节点的右节点,最后将指向当前节点的cur 移到最新节点
-
返回 res.right
上一篇: inline元素上支持的css属性