On Leetcode, I'm supposed to "flatten" a tree so that it becomes a "linked list."
/**
* Definition for a binary tree node.
* public 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;
* }
* }
*/
class Solution {
TreeNode result = new TreeNode(-1);;
public void flatten(TreeNode root) {
if (root == null) return;
solution1(root);
root = result.right;
}
public void solution1(TreeNode root) {
if (root != null) {
result.right = new TreeNode(root.val);
result = result.right;
if (root.left != null) solution1(root.left);
if (root.right != null) solution1(root.right);
}
}
}
The problematic lines of code is here:
result.right = new TreeNode(root.val);
result = result.right;
I'm trying to only add elements to the right side of the tree (so it looks like a linked list) but every time when I run my code, my "linked list" looks like an exact copy of the inputted tree.
If anyone could point me towards the right direction, I'd greatly appreciate it!
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ ^ that's the problem. The code I posted is my first "rundown" of what I think a naive solution might be.
Because of result = result.right;
your result
points to the last node you added.
So there's no pointer to your new root.
root = result.right;
does effectively nothing because you re-assign the parameter and never use it (btw: you should avoid re-assigning parameters, create local variables).
You can modify your solution1
(after first if
) and root
points to your LinkedList
:
if (this.result == null) {
this.result = new TreeNode(root.val);
this.pointer = this.result;
} else {
this.pointer.right = new TreeNode(root.val);
this.pointer = this.pointer.right;
}
TreeNode pointer;
is a new class member.
result
is not initialized so it's null
at first iteration.