Leetcode100.+Leetcode572.+Leetcode437. 分治法比较二叉树结构+求解路径_分治法求二叉树是否相等

Leetcode100. Same Tree

题目

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

解题分析

这道题题目要求非常简单，就是要让我们比较两棵二叉树是否相同。我们知道，两棵二叉树相同，必须树的结构和对应节点的值完全相同。因此，我们先来考虑特殊情况，如果两棵树都为NULL，则返回true；如果有一棵树为NULL，另一棵树不为NULL，那么就返回false。接下来我们来考虑更为一般的情况，如果两棵树都不为NULL，那么就比较这两个节点的值是否相同，如果不同，直接返回false；如果相同，再分别比较其左子树和右子树，得出最后的结果。

源代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p != NULL && q != NULL) {
            if (p->val != q->val) {
                return false;
            }
            if(!isSameTree(p->left, q->left)) {
                return false;
            }
            return isSameTree(p->right, q->right);
        }
        else if ((p == NULL && q != NULL) || (p != NULL && q == NULL)) {
            return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Leetcode572. Subtree of Another Tree

题目

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.

解题分析

这道题跟上面一道很类似，区别在于上一道只要让我们判断两棵二叉树是否相同就可以了，而这道题要求我们判断其中一棵树是否为另一棵树的子树，那这样情况就稍微复杂一些了。同样我们先来考虑特殊情况，如果树s为空，则说明无论树t是否为空，树t都不可能为树s的子树。
那接下来要怎么考虑呢？我们知道，要想判断树t是否为树s的子树，只需判断树t是否与树s的某一子树相同即可。判断两棵树是否相同的方法与上面一样，在此不再赘述。因此，只需要将树s进行遍历，判断它的左子树或右子树是否与树t相同即可。

源代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == NULL) {
            return false;
        }
        if (isSameTree(s, t)) {
            return true;
        }
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p != NULL && q != NULL) {
            if (p->val != q->val) {
                return false;
            }
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
        else if ((p == NULL && q != NULL) || (p != NULL && q == NULL)) {
            return false;
        }
        return true;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Leetcode437. Path Sum III

题目

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

解题分析

这道题跟上面也比较类似，主要是用到分治的思想。题目要求我们输出所有和为sum的路径的总数，因此，我们就要分别判断当前节点所在的树及其左右子树是否存在满足要求的路径。同样，判断左右子树是否存在路径满足要求需要用到递归的思想，而在判断当前树是否存在路径的过程中，如果当前节点的值与sum相同，则path加1，同时继续向下遍历树，直到该树所有节点都被访问为止。

源代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return 0;
        }
        return path(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
    }

    int path(TreeNode* root, int sum) {
        if (root == NULL) {
            return 0;
        }
        return (root->val == sum ? 1 : 0) + path(root->left, sum - root->val) + path(root->right, sum - root->val);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

以上是我对这三道问题的一些想法，有问题还请在评论区讨论留言~