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

  • 1

    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;
        public void flatten(TreeNode root)
            final TreeNode newRoot = new TreeNode(0);
            newRoot.right = root;
            previous = newRoot;

Log in to reply

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