26.树的子结构.md

26.树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构:

思路 & 解答

先找到相同的根节点，然后递归判断左子树和右子树即可，对于根节点而言，只要有一个为空，就不匹配。如果从根节点开始匹配并且匹配上了，那么就返回true，否则，使用左/右子节点当成根节点匹配。

匹配的过程同样是递归，根节点相同的时候，需要递归判断左子树和右子树。

代码如下：

public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
    // 只要一个为null，则返回false
    if (root1 == null || root2 == null) {
        return false;
    }
    // 从当前根节点比较
    if (sameTree(root1, root2)) {
        return true;
    } else {
        // 否则分别使用左子树或者右子树与root2匹配
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

}

public static boolean sameTree(TreeNode root1, TreeNode root2) {
    // 这里需要注意，当子结构遍历结束的时候，应该返回true
    if ( root2 == null) {
        return true;
    }
    if (root1 != null && root2 != null) {
        if (root1.val == root2.val) {
            return sameTree(root1.left, root2.left) && sameTree(root1.right, root2.right);
        } else {
            return false;
        }
    }
    return false;
}

C++ 代码如下：

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

    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
public:
    bool HasSubtree(TreeNode *root1, TreeNode *root2) {
        // 只要一个为null，则返回false
        if (root1 == NULL || root2 == NULL) {
            return false;
        }
        // 从当前根节点比较
        if (sameTree(root1, root2)) {
            return true;
        } else {
            // 否则分别使用左子树或者右子树与root2匹配
            return HasSubtree(root1->left, root2) || HasSubtree(root1->right, root2);
        }
    }

    bool sameTree(TreeNode *root1, TreeNode *root2) {
        // 这里需要注意，当子结构遍历结束的时候，应该返回true
        if (root2 == NULL) {
            return true;
        }
        if (root1 != NULL && root2 != NULL) {
            if (root1->val == root2->val) {
                return sameTree(root1->left, root2->left) && sameTree(root1->right, root2->right);
            } else {
                return false;
            }
        }
        return false;
    }
};

时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量 空间复杂度 O(M) ： 当树 A 和树 B`` 都退化为链表时，递归调用深度最大。取树A的深度`M`。

上面是递归版本，如何使用非递归解决这个问题呢？

实际上也并非严格意义上的递归，在判断是否相同的时候，依旧使用了递归的解法，只是在进行根节点对比的时候，使用了队列来存储所有的节点。

Java代码实现如下：

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (isSame(current, root2)) return true;
            else {
                if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
        }
        return false;
    }

    public boolean isSame(TreeNode root1, TreeNode root2) {
        if (root2 == null) return true;
        if (root1 == null) return false;
        return root1.val == root2.val
                && isSame(root1.left, root2.left)
                && isSame(root1.right, root2.right);
    }
}

C++代码实现如下：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode *root1, TreeNode *root2) {
        if (root1 == NULL || root2 == NULL) {
            return false;
        }
        deque<TreeNode *> myQuque;
        myQuque.push_back(root1);
        while (myQuque.size() != 0) {
            TreeNode *current = myQuque.front();
            myQuque.pop_front();
            if (isSame(current, root2)) return true;
            else {
                if (current->left != NULL) myQuque.push_back(current->left);
                if (current->right != NULL) myQuque.push_back(current->right);
            }
        }
        return false;
    }

    bool isSame(TreeNode *root1, TreeNode *root2) {
        if (root2 == NULL) return true;
        if (root1 == NULL) return false;
        return root1->val == root2->val
               && isSame(root1->left, root2->left)
               && isSame(root1->right, root2->right);
    }
};