Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/114.html

Given the root of a binary tree, flatten the tree into a "linked list":

  • The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The "linked list" should be in the same order as a pre-order traversal of the binary tree.

 

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -100 <= Node.val <= 100

 

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Algorithm

DFS

To move the leftmost child node to its parent’s position in a binary tree, we can use the depth-first search (DFS) approach. First, we find the leftmost child node by recursively traversing the left child nodes. Once we reach the leftmost child node, we move back up to its parent node.

To perform the node swap, we disconnect the parent node from its right child node and connect the original left child node to the right child node of the parent node. Then, we connect the original right child node to the right child node of the new right child node. We repeat this operation for each parent node until we have swapped all leftmost child nodes.

Although simple, there are still a few pits

  1. One pitfall to avoid is not properly maintaining a tail node during the traversal. To ensure we add each node to the end of the list, we must save both the left and right child nodes and add them to the tail node.
  2. Additionally, we need to update the tail node every time we add a new node and set the left child node to null, to ensure we only add the right child node to the list.

Flatten process:

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Iteration

Starting from the root node, first check whether its left child node exists, if it exists, disconnect the root node from its right child node, and connect the left child node and all the structures behind it to the original right child node. Connect the original right child node to the last right child node of the meta left child node.

Code

  • import java.util.Stack;
    
    public class Flatten_Binary_Tree_to_Linked_List {
    
    	/**
    	 * Definition for a binary tree node.
    	 * public class TreeNode {
    	 *     int val;
    	 *     TreeNode left;
    	 *     TreeNode right;
    	 *     TreeNode(int x) { val = x; }
    	 * }
    	 */
        public class Solution {
            public void flatten(TreeNode root) {
    
                // pre-order traversal
                if (root == null) {
                    return;
                }
    
                Stack<TreeNode> sk = new Stack<>();
                sk.push(root);
    
                TreeNode prev = new TreeNode(0);
    
                while (!sk.isEmpty()) {
                    TreeNode current = sk.pop();
    
                    if (current.right != null) {
                        sk.push(current.right);
                    }
                    if (current.left != null) {
                        sk.push(current.left);
                    }
    
                    prev.left = null; // cut off
                    prev.right = current;
    
                    prev = current;
                }
            }
        }
    
    
        public class Solution_recursion {
    
            TreeNode prev = new TreeNode(0);
    
            public void flatten(TreeNode root) {
    
                // pre-order traversal, iteration, then every time stack pop, append to list end
                // maintain the tail node
    
                if (root == null) {
                    return;
                }
    
                TreeNode left = root.left;
                TreeNode right = root.right;
    
                // update tail node
                prev.right = root;
                prev.left = null; // @note@note: this is key, cut off left, or "time limit" error
                prev = root;
    
                if (left != null) flatten(left);
                if (right != null) flatten(right);
    
    
            }
        }
    
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public void flatten(TreeNode root) {
            while (root != null) {
                if (root.left != null) {
                    TreeNode pre = root.left;
                    while (pre.right != null) {
                        pre = pre.right;
                    }
                    pre.right = root.right;
                    root.right = root.left;
                    root.left = null;
                }
                root = root.right;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        TreeNode* dfs(TreeNode* root) { // returns a pointer to the last node after flattening
            if (!root || (!root->left && !root->right)) return root;
            auto leftLast = dfs(root->left), rightLast = dfs(root->right), left = root->left, right = root->right;
            root->left = nullptr;
            root->right = left ? left : right;
            if (left) leftLast->right = right;
            return right ? rightLast : leftLast;
        }
    public:
        void flatten(TreeNode* root) {
            dfs(root);
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution: # no stack
        def flatten(self, root: Optional[TreeNode]) -> None:
            """
            Do not return anything, modify root in-place instead.
            """
            while root:
                if root.left:
                    pre = root.left
                    while pre.right:
                        pre = pre.right
                    pre.right = root.right
                    root.right = root.left
                    root.left = None
                root = root.right
    
    
    class Solution: # stack, pre-order interation
        def flatten(self, root: TreeNode) -> None:
            """
            Do not return anything, modify root in-place instead.
            """
            if not root:
                return
            
            stack = [root]
            prev = TreeNode(0)
            
            while stack:
                current = stack.pop()
                
                if current.right:
                    stack.append(current.right)
                if current.left:
                    stack.append(current.left)
                    
                prev.left = None
                prev.right = current
                
                prev = current
    
    
    ############
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        
        def __init__(self):
            self.prev = TreeNode(0)
    
        def flatten(self, root: TreeNode) -> None:
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            if not root:
                return
            
            left = root.left
            right = root.right
            
            self.prev.right = root
            self.prev.left = None # cut
            self.prev = root
            
            if left:
                self.flatten(left)
            if right:
                self.flatten(right)
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func flatten(root *TreeNode) {
    	for root != nil {
    		left, right := root.Left, root.Right
    		root.Left = nil
    		if left != nil {
    			root.Right = left
    			for left.Right != nil {
    				left = left.Right
    			}
    			left.Right = right
    		}
    		root = root.Right
    	}
    }
    
    
  • /**
     * Definition for a binary tree node.
     * class TreeNode {
     *     val: number
     *     left: TreeNode | null
     *     right: TreeNode | null
     *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.left = (left===undefined ? null : left)
     *         this.right = (right===undefined ? null : right)
     *     }
     * }
     */
    
    /**
     Do not return anything, modify root in-place instead.
     */
    function flatten(root: TreeNode | null): void {
        while (root != null) {
            if (root.left != null) {
                let pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
    
    
  • /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {void} Do not return anything, modify root in-place instead.
     */
    var flatten = function (root) {
        while (root) {
            if (root.left) {
                let pre = root.left;
                while (pre.right) {
                    pre = pre.right;
                }
                pre.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    };
    
    
  • // Definition for a binary tree node.
    // #[derive(Debug, PartialEq, Eq)]
    // pub struct TreeNode {
    //   pub val: i32,
    //   pub left: Option<Rc<RefCell<TreeNode>>>,
    //   pub right: Option<Rc<RefCell<TreeNode>>>,
    // }
    // 
    // impl TreeNode {
    //   #[inline]
    //   pub fn new(val: i32) -> Self {
    //     TreeNode {
    //       val,
    //       left: None,
    //       right: None
    //     }
    //   }
    // }
    use std::rc::Rc;
    use std::cell::RefCell;
    impl Solution {
        #[allow(dead_code)]
        pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
            if root.is_none() {
                return;
            }
            let mut v: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
            // Initialize the vector
            Self::pre_order_traverse(&mut v, root);
            // Traverse the vector
            let n = v.len();
            for i in 0..n - 1 {
                v[i].as_ref().unwrap().borrow_mut().left = None;
                v[i].as_ref().unwrap().borrow_mut().right = v[i + 1].clone();
            }
        }
    
        #[allow(dead_code)]
        fn pre_order_traverse(v: &mut Vec<Option<Rc<RefCell<TreeNode>>>>, root: &Option<Rc<RefCell<TreeNode>>>) {
            if root.is_none() {
                return;
            }
            v.push(root.clone());
            let left = root.as_ref().unwrap().borrow().left.clone();
            let right = root.as_ref().unwrap().borrow().right.clone();
            Self::pre_order_traverse(v, &left);
            Self::pre_order_traverse(v, &right);
        }
    }
    

All Problems

All Solutions