Easy Java solution in two different ways with full explanation


  • 0
    L

    This problem can be solved in multiple ways as you could see other threads. However, I will explain how I did with 2 different ways that include pre and post orders. The tricky part of this problem is to combine the left and right nodes with the root after propagating it back to the root at the top.

    Using Post Order

    This is elegant since it just needs one global pointer. The trick here is that you find the end of the list and then come back to find the previous. This requires traversing the right child first and then when you come to the left, you already know its next pointer. Here is the code for that:

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

    Pay attention to the fact that you need to set root.left=null to avoid hangs and runtime errors in leetcode.

    Using PreOrder Traversal

    This approach will traverse the left and then right child. At each traversal one should know what is the start and end points. We just join them together at each level and by the time it is propagated to the top, we have a joined list. Here is the code:

        public void flatten(TreeNode root) {
            if (root == null){
              return;
            }
            helper(root);
        }
    
      private Wrapper helper(TreeNode root) {
        if (root.left == null && root.right == null) {
          return new Wrapper(root, root);
        }
        Wrapper left = null;
        Wrapper right = null;
        Wrapper current = new Wrapper(root, null);
        if (root.left != null){
          left = helper(root.left);
        }
        if (root.right != null){
          right = helper(root.right);
        }
        root.left = null;
        if (left != null){
          root.right = left.start;
          current.end = left.end;
        }
        if (right != null){
          if (left != null){
            left.end.right = right.start;
          }
          current.end = right.end;
        }
        return current;
      }
    
      private class Wrapper {
            private TreeNode start;
            private TreeNode end;
            Wrapper(TreeNode start, TreeNode end){
              this.start = start;
              this.end = end;
          }
     }
    
    

Log in to reply
 

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