BFS solution using queue + explanation


  • 0
    S
    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if(t1 == null)
                return t2;
            if(t2 == null)
                return t1;
            
            Queue<TreeNode[] > queue = new LinkedList<>();  
            queue.add(new TreeNode[] {t1, t2});
            while(!queue.isEmpty()) {
                TreeNode[] nodes = queue.remove();
                // If right tree has a null value for a node, then we dont need to change anything in the left tree
                if(nodes[1] != null) {
                    nodes[0].val += nodes[1].val; // Since the node exists in the right tree, lets add it to the left tree
                    
                    // If left node of 1st tree is null, then we just point to the left node of the 2nd tree
                    if(nodes[0].left == null) {
                        nodes[0].left = nodes[1].left;
                    } else {
                        queue.add(new TreeNode[] {nodes[0].left,nodes[1].left});
                    }
                    
                    // If right node of 1st tree is null, then we just point to the right node of the 2nd tree
                    if(nodes[0].right == null) {
                        nodes[0].right = nodes[1].right;
                    } else {
                        queue.add(new TreeNode[] {nodes[0].right, nodes[1].right});
                    }
                }
            }
            
            // Return t1, as we have been updating the nodes of t1 instead of creating a new tree
            return t1;
        }
    }
    

Log in to reply
 

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