My short post order traversal Java solution for share


  • 420
    T
    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;
    }

  • 4
    S

    It took a while to get the idea. Man it is beautiful!


  • 0

    Omg that's so clever


  • 1
    B

    This is so freaking beautiful.


  • 0
    This post is deleted!

  • 16
    W

    Great idea! Just for clarify, this is not post order. this is 'reversed' preorder.


  • 95
    K

    This is really brilliant! But flatten() would be unreusable if prev is set to a field. Here's another way of implementing the same idea.

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

  • 8
    Y

    Can you give us a little hint about how you come up with this idea?


  • 0
    R

    good solution ......


  • 0
    L

    This is bottom-up recursion, brilliant!


  • 7
    S

    You go right first and I go left first. lol.

    public class Solution {
        private static TreeNode pointer = null;
        
        public void flatten(TreeNode root) {
            if(root == null)
                return;
                
            if(pointer != null)
                pointer.right = root;
            
            pointer = root;
                
            TreeNode right = root.right;
            flatten(root.left);
            root.left = null;
            flatten(right);
        }
    }

  • 3
    H

    can you explain how you come up with this idea which is so outgoing and unbelievable and i am confused about that.


  • 0
    C

    What a brilliant answer!


  • 1
    C

    So it is time to show my C++ Solution. 8ms From right to left.

    	class Solution {
        public:
    	    void flatten(TreeNode* root) {
    	
    		    helper(root);
    	    }
        private:
    	    TreeNode* prev = NULL;
    	    void helper(TreeNode* root)
    	    {
    		    if (root == NULL)
    		   	    return;
    		    helper(root->right);
    		    helper(root->left);
    		    root->right = prev;
    		    root->left = NULL;
    		    prev = root;
    	    } 
        };

  • 0
    C
    //I also write an answer dealing the tree from left to right.
    
    
    class Solution {
    public:
    void flatten(TreeNode* root) {
    	if (!root)
    		return;
    	helper(root);
    }
    private:	
    void helper(TreeNode* root)
    {
    	if (!root)
    		return;
    	if (!root->left && !root->right)
    		return;
    	else if (root->left == NULL && root->right != NULL)
    		helper(root->right);
    	else if (root->right == NULL && root->left != NULL)
    	{
    		helper(root->left);
    		root->right = root->left;
    		root->left = NULL;
    	}
    	else
    	{
    		helper(root->left);
    		helper(root->right);
    		TreeNode* p = root->right;
    		root->right = root->left;
    		root->left = NULL;
    		TreeNode* q = root->right;
    		while (q->right != NULL)
    			q = q->right;
    		q->right = p;
    	}
    } };

  • 0
    R
    This post is deleted!

  • 0
    R

    So the time complexity is O(n)?


  • 0
    W

    活捉凯冰,答案很厉害,鼓掌鼓掌


  • 0
    K

    lol阁下是?。。。。。。。。


  • 0
    G

    I think the complexity is O(n) because you visit every node just once.


Log in to reply
 

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