leetcode 617. Merge Two Binary Trees

4527 ワード

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees. 熱を出したら頭が悪いような気がします.もしroot.left=nullの場合、DFS(root.left,t 1,left,t 2.left)を行い、root=rootに進む.leftのDFSメソッドでroot=new TreeNode(2);このような付与の場合、最終的な結果はrootである.left=null、すなわち、関数呼び出しを行うと、入力関数のroot.leftは賦課を行い、new TreeNodeもnullも賦課しても、少しも卵用がなく、rootを変えることはない.leftの結果.rootに直接しか対応できません.leftは値を割り当てますが、関数に入力して関数に値を割り当てることはできません.私はとても複雑にやった.
package leetcode;

public class Merge_Two_Binary_Trees_617 {

	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
		if(t1==null){
			t1=t2;
			return t1;
		}
		else if(t2==null){
			return t1;
		}
		TreeNode root=new TreeNode(0);
		DFS(null,false,root,t1,t2);
		return root;
	}
	
	public void DFS(TreeNode before,boolean isLeft,TreeNode root,TreeNode t1, TreeNode t2){
		if(t1!=null&&t2!=null){
			root.val=t1.val+t2.val;
			root.left=new TreeNode(0);
			root.right=new TreeNode(0);
			DFS(root,true,root.left,t1.left,t2.left);
			DFS(root,false,root.right,t1.right,t2.right);
		}
		else if(t1!=null&&t2==null){
			root.val=t1.val;
			root.left=new TreeNode(0);
			root.right=new TreeNode(0);
			DFS(root,true,root.left,t1.left,null);
			DFS(root,false,root.right,t1.right,null);
		}
		else if(t1==null&&t2!=null){
			root.val=t2.val;
			root.left=new TreeNode(0);
			root.right=new TreeNode(0);
			DFS(root,true,root.left,null,t2.left);
			DFS(root,false,root.right,null,t2.right);
		}
		else{
			if(isLeft==true){
				before.left=null;
			}
			else{
				before.right=null;
			}		
			return;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Merge_Two_Binary_Trees_617 m=new Merge_Two_Binary_Trees_617();
		TreeNode root1=new TreeNode(1);
		root1.left=new TreeNode(3);
		root1.right=new TreeNode(2);
		root1.left.left=new TreeNode(5);
		TreeNode root2=new TreeNode(2);
		root2.left=new TreeNode(1);
		root2.right=new TreeNode(3);
		root2.left.right=new TreeNode(4);
		root2.right.right=new TreeNode(7);
		TreeNode t=m.mergeTrees(root1, root2);
		System.out.println(1);
	}

}
大神解法は簡潔で、再帰と反復を用いた.
再帰:
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}
反復:もちろんスタックが使用されます.
再帰の代わりにスタックを用いる、各スタック要素は[node_{tree 1},node_{tree 2}][node tree 1,node tree 2]形式のデータを格納する.ここでnode_{tree 1}node tree 1はtree 1のnode,node_{tree 2}node tree 2はtree 2のnodeである.
に会うhttps://leetcode.com/problems/merge-two-binary-trees/#/solutionに表示されます.
public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        Stack < TreeNode[] > stack = new Stack < > ();
        stack.push(new TreeNode[] {t1, t2});
        while (!stack.isEmpty()) {
            TreeNode[] t = stack.pop();
            if (t[0] == null || t[1] == null) {
                continue;
            }
            t[0].val += t[1].val;
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.push(new TreeNode[] {t[0].left, t[1].left});
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.push(new TreeNode[] {t[0].right, t[1].right});
            }
        }
        return t1;
    }
}