LeetCode：二叉树相关应用

LeetCode：二叉树相关应用

基础知识

617.归并两个二叉树

题目

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.

分析

以t1树为基础展开归并，首先两树都进行先序遍历，在遍历的过程中，如果发现一方当前节点不存在，则用另一者的节点桥接过来，如果两者都存在，则计算其和。

这里有两个小思考点：

　　如果t1节点有，而t2节点没有，那么无须进行其他操作，并且t1节点的当前子节点都无需遍历，因为t2全都不存在。同理，t1没有，t2桥接过来，所有的子节点都无需再遍历。　　

本题主要考察了二叉树的线性存储的先序遍历、递归思想。

标准题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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;
    }
}