题目
文章来源:https://www.toymoban.com/news/detail-683976.html
方法一:前序遍历(构造集合) + 集合(构造新树)
List<TreeNode> res = new ArrayList<>();
public void flatten(TreeNode root) {
dfs(root);
for(int i = 0 ; i <res.size() ; i++){
if(i == res.size()-1){//处理最后一个节点
res.get(i).left = null;
res.get(i).right = null;
break;
}
res.get(i).left = null;
res.get(i).right = res.get(i+1);
}
}
//前序遍历
public void dfs(TreeNode root) {
if(root == null ) return ;
res.add(root);
dfs(root.left);
dfs(root.right);
}
方法二:原地构建
- 将左子树插入到右子树的地方
- 将原来的右子树接到左子树的最右边节点
- 考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null
public void flatten(TreeNode root) {
while(root !=null){
//左子树为 null,直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while(pre.right !=null){
pre =pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}
文章来源地址https://www.toymoban.com/news/detail-683976.html
方法三:前序遍历–迭代(构造集合) + 集合(构造新树)
public void flatten(TreeNode root) {
List<TreeNode> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty() || root != null){
while(root != null) {
res.add(root);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
for(int i = 0 ; i <res.size() ; i++){
if(i == res.size()-1){//处理最后一个节点
res.get(i).left = null;
res.get(i).right = null;
break;
}
res.get(i).left = null;
res.get(i).right = res.get(i+1);
}
}
到了这里,关于【LeetCode-中等题】114. 二叉树展开为链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!