Solve it using a queue and post-order-traversal , Java


  • 1
    G

    public class Solution {

    public void flatten(TreeNode root) {
        if(root == null){return;}
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        dfs(root, queue);
        TreeNode pre = queue.remove();
        pre.left = null;
        pre.right = null;
        while(queue.size() != 0){
            TreeNode temp = queue.remove();
            temp.right = pre;
            temp.left = null;
            pre = temp;
        }
    }
    
    public void dfs(TreeNode root, Queue<TreeNode> queue){
        if(root == null){return;}
        if(root.right != null){
            dfs(root.right, queue);
        }
        if(root.left != null){
            dfs(root.left, queue);
        }
        queue.add(root);
    }

  • 0

    Get the same idea with you...


  • 0
    B

    Think we need to do it in-place? No extra space?


  • 0
    G

    Oh, you are right! thanks for telling me..


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.