javabinary-treepostorder

Only adding elements to the right side of the tree


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.


Solution

  • 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.