leetcode100.相同的树，101对称二叉树

相同的树

思路一：序列化

将两棵树进行序列化，然后比较序列化后的字符串即可，相同返回true,不同返回false;
代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        String pStr = serializeTreeByPreOrder(p);
        String qStr = serializeTreeByPreOrder(q);
        return pStr.equals(qStr);
    }

    private static String serializeTreeByPreOrder(TreeNode root){
        if(root == null){
            return "#_";
        }
        String res = root.val + "_";
        res += serializeTreeByPreOrder(root.left);
        res += serializeTreeByPreOrder(root.right);
        return res;
    }
}

时间复杂度：因为序列化操作需要遍历二叉树，所以时间复杂度为O(N)

额外空间复杂度：使用了字符串去保存序列化的二叉树每个节点值，额外空间复杂度为O(N)

执行结果：

思路二：recursion

递归的思路如下：

判断两个指针当前节点值是否相等
判断 A 的左子树与 B 的左子树是否相等
判断 A 的右子树与 B 的右子树是否相等

代码如下：

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

        if(p == null || q == null){
            return false;
        }

        return (p.val == q.val)
                    && isSameTree(p.left,q.left)
                    && isSameTree(p.right,q.right);
    }
}

时间复杂度：O(N)

额外空间复杂度：最大的递归深度是当二叉树退化为线性链表的时候，额外空间复杂度为O(N)

执行结果：

对称二叉树

题目链接

思路一：序列化

对于一棵对称的二叉树：

它的先序遍历的结果为：1,2,3,4,2,4,3
先序遍历的顺序为 node->node.left->node.right;

如果遍历的顺序为 node->node.right->node.left;
那么这种方式遍历的结果为：1,2,3,4,2,4,3 同先序遍历结果一致
所以，可以用二叉树序列化的思想，使用先序和类似于后序遍历的思路将树序列化之后进行比对，结果相同则说明树是对称的。
代码如下：

/**
 * 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) {
        String res1 = serializeTreeByPreOrder(root);
        String res2 = serializeTreeByPosOrder(root);
        return res1.equals(res2);

    }

    private static String serializeTreeByPreOrder(TreeNode root){
        if(root == null){
            return "#_";
        }
        String res = root.val + "_";
        res += serializeTreeByPreOrder(root.left);
        res += serializeTreeByPreOrder(root.right);
        return res;
    }

    private static String serializeTreeByPosOrder(TreeNode root){
        if(root == null){
            return "#_";
        }
        String res = root.val + "_";
        res += serializeTreeByPosOrder(root.right);
        res += serializeTreeByPosOrder(root.left);
        return res;
    }
}

该算法的时间复杂度为：O(N)；因为对二叉树序列化需要遍历每一个节点

额外空间复杂度为：O(N)；额外使用了字符串保存二叉树的所有节点的值

执行结果：

思路二： recursion

递归思路：

判断两个指针当前节点值是否相等
判断 A 的右子树与 B 的左子树是否对称
判断 A 的左子树与 B 的右子树是否对称

代码如下：

/**
 * 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) {
        return isMirror(root,root);
    }

    private boolean isMirror(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1 == null || root2 == null){
            return false;
        }

        return (root1.val == root2.val)
                    && (isMirror(root1.left,root2.right))
                    && (isMirror(root1.right,root2.left));
    }
}

时间复杂度:O(N)
额外空间复杂度:当二叉树退化为线性的链表时，额外空间复杂度为O(N)
执行结果：

最后编辑于：2020.05.12 11:54:18