树的子结构

medium 原题连接：树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

​ 3
​ / \

4 5
/
1 2
给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例：

输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

  1. 0 <= 节点个数 <= 10000

解题思路

证明一个树B是另一棵树A的子结构，按顺序要证明两点：

  1. 找到 B 的根节点在 A 中的位置
  2. 在根节点正确的前提下，只要 B 不为null的地方，A 都应该与其值相同

接下来就是分析遍历：

  1. 明确一个rootNode函数，作用是判断传入的B节点是否是A的子结构，与主方法不同的是，前者只要判断根节点这一个节点，后者需要遍历判断整个B子树。
  2. 将子结构判断交给rootNode，主方法要做的就是遍历 A 判断和 B 根节点相同的节点：判断当前节点 - 判断左节点 - 判断右节点
  3. rootNode函数递归判断当前节点值，左节点值，右节点值是否和 A 中一致

注：主函数中最后递归 return 使用的条件是 || 或，因为只要判断是子结构就行，不用在意有几次子结构，所以如果前者返回true，后者就不用计算了，而rootNode方法则需要完整的判断B的全部节点都在A中，所以return条件为 && 与

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B==null) return false;
        if(A.val == B.val && rootNode(A.left, B.left) && rootNode(A.right, B.right)) {
            return true;
        }
        return (isSubStructure(A.left, B) || isSubStructure(A.right, B));

    }

    // 判断节点B是否为A的子结构
    public boolean rootNode(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return (rootNode(A.left, B.left) && rootNode(A.right, B.right));
    }
}

二叉树的镜像

Easy 原题连接：二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

​ 4

/
2 7
/ \ /
1 3 6 9
镜像输出：

​ 4

/
7 2
/ \ /
9 6 3 1

示例：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

提示：

  1. 0 <= 节点个数 <= 1000

解题思路

这里涉及到一个二叉树遍历问题，详情可以看我这篇博客：二叉树 | IT蛋的个人博客 (xcscx.github.io)

简单来说，二叉树在遍历时会三次经过当前节点，以先序遍历做例子分别是：第一次访问、从访问的左节点返回、从访问的右节点返回

对于像本题中的全反问题，其实就是从叶子节点开始，将自己的左右子树对换，递推回根节点，那么什么时候兑换呢

替换发生在第一次，或者最后一次访问当前节点较好

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root; 
        mirrorTree(root.right);
        mirrorTree(root.left);
        TreeNode mid = root.right;
        root.right = root.left;
        root.left = mid;
        return root;
    }
}

对称的二叉树

Easy 原题连接：对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

​ 1

/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

​ 1

/
2 2
\
3 3

示例：

输入：root = [1,2,2,3,4,4,3]
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

  • 0 <= 节点个数 <= 1000

解题思路

交换判断左右子树的左右子树，即先判断左右子树是否相等，再将左子树的左右子树和右子树的右左子树递归以上判断

直到双方同时为 null 返回 true

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSonOk(root.left, root.right);
    }

    public boolean isSonOk(TreeNode A, TreeNode B) {
        if(A == null && B == null) return true;
        if(A == null || B == null || A.val != B.val) return false;
        return (isSonOk(A.left, B.right) && isSonOk(A.right, B.left));
    }
}