A VERY VERY detailed explanation of the highest-voted solution and some interesting thoughts about it.


  • 0

    Lemme try to explain @tusizi 's idea a little bit, based on his code snippet.

    As you can see, the problem asks for a linkedlist-alike result. To build a linked list recursively, let's say we have reached recursion depth d, we need to set the current node cur 's next attribute as the return value of recursion call d+1. And we return cur, which will be used in d-1 recursion. Pretty much like that.

    Similarly, for this problem, we also need to find the current node's next node. For this problem, we use TreeNode prev to hold the next node (I must say, I'd prefer it is named as next or something.) The difference from above is that, instead of returning the next node, @tusizi uses a global variable to maintain the next node. The reason will be stated in the following. But I have point out, I agree with @cifer-lee , it remains to be discussed if it is a good way for doing so, but for now let's just assume it is. In the following, I will use linked list or tree, head or root, right or next, interchangeably.

    Let's inspect the execution process of @tusizi 's code snippet a little bit.

    private TreeNode prev = null;
    
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
    

    After flatten(root.right), we have processed the right branch of the current node, and the current prev is the head of root of the right branch. For now, we want to know which node is the precedent node of prev, and we will set this particular node's next attribute as prev. As per the problem, this particular node is actually the rightmost node of the left branch.

    Next, let's say why we can actually get it. So now we go to the next line, which is flatten(root.left). When we go deeper and deeper in the recursion, we are actually going right because we go right before we go left. A small remark here, the traversal order of the code snippet is actually right->left->cur, not post-order, more like reversed post order if you like. As we are going right, we will stop when we cannot go right furthermore. Then we set right or next attribute of the current node as prev, which is exactly what we want.

    Now let's go back to the original function call layer, we have done flatten(root.right) and flatten(root.right). The remaining is easy, we set the root node's next node as prev, which is the head of the left branch. Done!

    A little more comment on why we cannot return the current node like what we do in linked list for this solution. The short answer is that tree is non-liner. The more verbose answer is that we want to connect the rightmost node on the left branch to the leftmost node on the right branch, this is something that we cannot achieve in the current layer directly. If we insist on returning value, we may need to traverse the left branch on our own, and then do the same connection stuff. This is what a lot other solutions are doing, like this one hanzhou87's solution. My solution is to return the end node of left branch directly. The following is my solution in Python.

    class Solution(object):
        def flatten(self, root):
            if not root:
                return
    
            def _helper(node):
                r_end = l_end = None
                if node.right:
                    r_start, r_end = _helper(node.right)
                if node.left:
                    l_start, l_end = _helper(node.left)
                    l_end.right = node.right
                    node.right = l_start
                    # Clear left branch
                    node.left = None
    
                return (node, r_end or l_end or node)
    
            _helper(root)
    

    The following is the python version of the idea.

    class Solution(object):
        prev = None
        def flatten(self, root):
            if not root:
                return
            self.flatten(root.right)
            self.flatten(root.left)
            
            root.right = self.prev
            root.left = None
            self.prev = root
    

Log in to reply
 

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