剑指offer 26 树的非递归遍历

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

解题思路

C语言的非递归方法. 可能是测试用例中没有深层次的二叉树(10000个节点的最大深度13), 因此内存使用优势没有展现出来. 深层次反复调用递归肯定是内存爆表的.

整体思路和树的非递归遍历方法一致, 将符合要求的节点存储起来(本方法使用了Tree链表结构保存节点信息),在下一次的循环中取出检查

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct Tree {
    struct TreeNode *pos;
    struct Tree *next;
};

//工具函数: 向某个Tree中添加节点
void addNode(struct Tree *head, struct TreeNode *item)
{
    struct Tree *temp = (struct Tree*)malloc(sizeof(struct Tree));
    temp->pos = item;
    temp->next = head->next;
    head->next = temp;
}

//工具函数: 在某个Tree中取得一个TreeNode节点, 并释放Tree中所占空间
//本函数不检查是否为空!
struct TreeNode* findNode(struct Tree *head)
{
    struct Tree *temp =head->next;
    head->next = temp->next;
    struct TreeNode *result = temp->pos;
    free(temp);
    return result;
}

 //工具函数: 在A中找到起始位置, 将所有符合的起始位置都加入startA
 //如果没有找到, 则返回false
bool findPosition(struct Tree *startA, struct TreeNode *A, int val)
{
    struct TreeNode *pos = A;
    struct Tree *mark = (struct Tree*)malloc(sizeof(struct Tree));//先序遍历
    mark->next = NULL;
    while(pos)
    {
        while(pos)
        {
            if(pos->val == val)
                addNode(startA, pos);
            if(pos->right) addNode(mark, pos->right);
            pos = pos->left;
        }
        if(mark->next) pos = findNode(mark);
    }

    if(startA->next) 
        return true;
    else
        return false;
}


bool isSubStructure(struct TreeNode* A, struct TreeNode* B){
    if(A == NULL) return false;
    if(B == NULL) return false;
    int result = 1;
    struct Tree *checkA = (struct Tree*)malloc(sizeof(struct Tree));//对于每一个有起始节点的位置, checkA链表保存非递归
    struct Tree *checkB = (struct Tree*)malloc(sizeof(struct Tree));//同上
    struct Tree *startA = (struct Tree*)malloc(sizeof(struct Tree));//保存每一个符合起始值符合要求的节点
    startA->next = NULL;


    if(!findPosition(startA,A, B->val))//没有找到起始节点
        return false;


    while(startA->next)//对于每一个符合要求的起始节点开始遍历
    {
        result = 1;
        checkA->next = startA->next;//因为这里直接是将一个Tree节点从startA转移到checkA中, 因此不能使用findNode()(会被释放!)
        startA->next = checkA->next->next;

        checkB->next = NULL;    //重新初始化checkB链表
        addNode(checkB, B);
    
        
        while(checkB->next)//一直检查到checkB为空, 如果中途有不符合, 会提前退出并置result = 0
        {
            struct TreeNode *tempB = findNode(checkB);
            struct TreeNode *tempA = findNode(checkA);

            bool Ahas = (tempA->left), Bhas = (tempB->left);
            if(!Ahas && Bhas) //如果A无子树, 但是B有子树, 那么不符合. 下同
            {
                result = 0;
                break;
            }
            Ahas = (tempA->right), Bhas = (tempB->right);
            if(!Ahas && Bhas)
            {
                result = 0;
                 break;
            }

            //对比AB的左右子树
            if((tempA->left) && (tempB->left))
            {
                if(tempA->left->val != tempB->left->val)
                {
                    result = 0;
                    break;
                }
                addNode(checkA, tempA->left);//将左右子树加入checkA/B链表,等待下一次循环时检查
                addNode(checkB, tempB->left);
            }

             //可选择的优化策略: 只加入右子树, 左子树直接通过tempA/B = tempA/B->left并continue循环检查


             
            if((tempA->right) && (tempB->right))
            {
                if(tempA->right->val != tempB ->right->val)
                {
                    result = 0;
                    break;
                }
                addNode(checkA, tempA->right);
                addNode(checkB, tempB->right);
            }
         }
         if(result) return true;//循环结束时因为result==1, 表明全都匹配
            
    }
    return false;
}