题解 | #合并二叉树#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    //非递归版本
    //非递归就是用栈来模拟递归行为
    //本题需要两个栈，需要两个栈不是以为有两个二叉树，而是因为一个栈用来存节点，一个栈用来存节点的值（其实也可以用一个栈）
    //依然用前序遍历，其实本题使用前中后甚至层序遍历都没问题
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if(t1==NULL&&t2==NULL)
            return NULL;
        else if(t1==NULL)
            return t2;
        else if(t2==NULL)
            return t1;
        //排除掉特殊情况后，此时这两颗树都非空
        stack<int > dataStack;//数据栈
        stack<TreeNode*> nodeStack;//节点栈
        dataStack.push(t2->val);dataStack.push(t1->val);
        nodeStack.push(t2);nodeStack.push(t1);
        while(!dataStack.empty()&&!nodeStack.empty()){//栈非空时
            //每次各从数据栈和节点栈中成双的弹出两个节点
            int data1=dataStack.top();dataStack.pop();
            int data2=dataStack.top();dataStack.pop();
            TreeNode*node1=nodeStack.top();nodeStack.pop();
            TreeNode*node2=nodeStack.top();nodeStack.pop();
            node1->val=node1->val+node2->val;//根据题意都不为空时相加,这里为什么没有判断是否为空？因为我们在下面的处理中直接去掉为空的可能
            if(node1->right&&node2->right){//当两个树的右节点都存在时
                dataStack.push(node2->right->val);
                dataStack.push(node1->right->val);
                nodeStack.push(node2->right);
                nodeStack.push(node1->right);
            }
            else if(!node1->right){//如果t1树的右节点为空
                node1->right=node2->right;//直接替换
            }
            //如果t2树的右节点为空那什么也不做
            //对左子树同理
            if(node1->left&&node2->left){
                dataStack.push(node2->left->val);
                dataStack.push(node1->left->val);
                nodeStack.push(node2->left);
                nodeStack.push(node1->left);
            }
            else if(!node1->left){
                node1->left=node2->left;
            }
        }
        return t1;
    }
};