617. Merge Two Binary Trees

題目鏈接

617. Merge Two Binary Trees

題目分析

給定兩個(gè)二叉樹，返回一個(gè) 將對(duì)應(yīng)位置值相加后的二叉樹。

例如，樹A的頂點(diǎn)值為1，樹B的頂點(diǎn)值為2，那么返回的二叉樹的頂點(diǎn)值需要是3。

思路

頂點(diǎn)自然不用多說，直接相加就可以了。

按照習(xí)慣，先遍歷左節(jié)點(diǎn)。如果樹A和樹B都有左節(jié)點(diǎn)，那么直接相加，再遞歸當(dāng)前函數(shù)去判斷左節(jié)點(diǎn)的左節(jié)點(diǎn)。

若樹A和樹B任意一棵樹沒有左節(jié)點(diǎn)時(shí)，直接把有左節(jié)點(diǎn)遷移過來即可。
因?yàn)?，如果沒有左節(jié)點(diǎn)，不可能會(huì)有左節(jié)點(diǎn)的左節(jié)點(diǎn)，或左節(jié)點(diǎn)的右節(jié)點(diǎn)。
因此，直接照搬過來就可以了。

若兩顆樹都沒有左節(jié)點(diǎn)時(shí)，忽略，直接去算右節(jié)點(diǎn)，并遵從以上規(guī)則即可。

最終代碼

<?php
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    function mergeTrees($t1, $t2) {
        if(is_null($t1->val)&&is_null($t2->val)){
            return;
        }
        $t1->val += $t2->val;
        if($t1->left&&$t2->left){
            $this->mergeTrees($t1->left, $t2->left);
        }
        if(!$t1->left&$t2->left){
            $t1->left = $t2->left;
        }
        if($t1->right && $t2->right){
            $this->mergeTrees($t1->right, $t2->right);
        }
        if(!$t1->right&&$t2->right){
            $t1->right = $t2->right;
        }
        return $t1;
    }
}

若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。