My recursion code, using a class variable to record the previous pre-order traversal node.


  • 1
    L

    The idea is simple, we only need to pre-order travel the tree and set left child of every node to null, and right child is next pre-order traversal node. Instead of finding the next node, we can record the previous node we just past, and set it's right to current node:

    public class Solution
     {
        private TreeNode previous;
        private void flattenTree(final TreeNode root)
        {
            if (null != root)
            {
                final TreeNode left = root.left;
                final TreeNode right = root.right;
                
                previous.left = null;
                previous.right = root;
                previous = root;
                
                flattenTree(left);
                flattenTree(right);
            }
        }
        
        public void flatten(TreeNode root)
        {
            final TreeNode newRoot = new TreeNode(0);
            newRoot.right = root;
            previous = newRoot;
            
            flattenTree(root);
        }
    }

Log in to reply
 

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