Straightforward Java Solution


  • 104
    H
    public void flatten(TreeNode root) {
            if (root == null) return;
            
            TreeNode left = root.left;
            TreeNode right = root.right;
            
            root.left = null;
            
            flatten(left);
            flatten(right);
            
            root.right = left;
            TreeNode cur = root;
            while (cur.right != null) cur = cur.right;
            cur.right = right;
        }
    

    This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don't forget to set left child to null)


  • 0
    J

    recursion is a good way


  • 1
    H

    Great solution, thank you for sharing. I got the idea and then implemented it on my own.


  • 0
    F

    Good for you


  • 0
    J

    Pretty smart way to solve it. +1


  • 0
    M

    Clearest recursive solution I have ever seen


  • 0
    R

    Can someone tell me what is the time complecity of this solution?


  • 3
    H
    public void Flatten(TreeNode root) {
                solve(root, null);
            }
            TreeNode solve(TreeNode root, TreeNode last)    {
                if(root == null) return last;
                root.right = solve(root.left, solve(root.right, last));
                root.left = null;
                return root;
            }

  • 1
    F

    same idea, i prefer this one than the top 1 post.


  • 4
    A

    This is not O(N) though.


  • 0
    E
    This post is deleted!

  • 2
    X

    I think the solution has complexity O(nlogn)


  • 1

    Complexity is still O(n). You never visit a node more than twice if you think about it.


  • 0

    Very straight forward and easy to understand. Thanks!


  • 0
    W

    Your code is so clear and easy to understand!


  • 1
    Y

    similar idea

        public void flatten(TreeNode root) {
            flatTree(root);        
        }
        
        private TreeNode flatTree(TreeNode node) {
            if (null == node) return null;
            
            TreeNode rightTree = flatTree(node.right);  // 4-5-6
            TreeNode leftTree = flatTree(node.left);    // 2-3-4
            if (null != leftTree ) {
                // append right to left.
                TreeNode x = leftTree;
                while (x.right != null) {
                    x = x.right;
                }
                x.right = rightTree;
                node.right = leftTree;
            }
            else node.right = rightTree;
            
            node.left = null;
            
            return node;
        }
    

  • 0
    M

    @xiong6 Why the complexity is O(nlogn) ? Could you please explain it?


  • 0
    B

    @BetaGoGoGo Nope. It is o(n^2). Every time you traverse downward to the very end of the left branch end. Since the tree is serialized it will be O(n^2) no matter how balanced it originally was.


  • 0
    B

    @MrARang I think it is not o(nlog n). Please check my previous post. Please correct me if I made a mistake.


  • 0
    H

    @bxli127 Hi I think for a balanced tree the time is O(nlogn). let's say the balanced tree's height is 4, the 1st level counts 8 node visit, the 2nd level counts 4+4=8 , 3rd level 2+6, 4th level 1+7. so 8*4, 8 being the number of leaves and 4 the height. how do you think?


Log in to reply
 

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