资讯专栏INFORMATION COLUMN

[Leetcode] Same Tree Symmetric Tree 相同树 对称树

TZLLOG / 926人阅读

摘要:递归法复杂度时间空间递归栈空间思路如果两个根节点一个为空,一个不为空,或者两个根节点值不同,说明出现了不一样的地方,返回假。代码递归法复杂度时间空间递归栈空间思路其实和写法是一样的,是比较两个节点的两个左边,然后再比较两个节点的两个右边。

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.

递归法 复杂度

时间 O(N) 空间 O(h) 递归栈空间

思路

如果两个根节点一个为空,一个不为空,或者两个根节点值不同,说明出现了不一样的地方,返回假。如果两个节点都是空,则是一样的,返回真。然后我们再递归它们的左右节点,如果递归结果中一个或两个是假,就返回假。否则,说明左右子树都是完全一样的。

代码
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

2018/2

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

2018/10

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p != nil && q != nil {
        return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
    }
    return false
}
Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / 
  2   2
 /  / 
3  4 4  3

But the following is not:

    1
   / 
  2   2
      
   3    3
递归法 复杂度

时间 O(N) 空间 O(h) 递归栈空间

思路

其实和Same Tree写法是一样的,Same Tree是比较两个节点的两个左边,然后再比较两个节点的两个右边。而对称树是要判断左节点的左节点和右节点的右节点相同(外侧),左节点的右节点和右节点的左节点相同(内侧)。不过对称树是判断一棵树,我们要用Same Tree一样的写法,就要另写一个可以比较两个节点的函数。

注意,Leetcode中当根节点为空时,树也是对称的

代码
    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root == null ? true : helper(root.left, root.right);
        }
        
        private boolean helper(TreeNode node1, TreeNode node2){
            if(node1 == null && node2 == null){
                return true;
            }
            if(node1 == null || node2 == null || node1.val != node2.val){
                return false;
            }
            return helper(node1.left, node2.right) && helper(node1.right, node2.left);
        }
    }

2018/2

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return root is None or self.helper(root.left, root.right)
        
    def helper(self, node1, node2):
        if node1 is None and node2 is None:
            return True
        if node1 is None or node2 is None:
            return False
        return node1.val == node2.val and self.helper(node1.right, node2.left) and self.helper(node1.left, node2.right)
迭代法 复杂度

时间 O(N) 空间 O(h)

思路

因为该题本质就是二叉树遍历,所以我们也可以用迭代来解。这里用一个队列,两棵树按照对称的顺序加入节点,然后进行比较。

代码
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue queue1 = new LinkedList();
        Queue queue2 = new LinkedList();
        queue1.offer(root.left);
        queue2.offer(root.right);
        while(!queue1.isEmpty() && !queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            // 如果都是null,说明是相同的
            if(node1 == null && node2 == null){
                continue;
            }
            // 如果有一个是null,或者值不同,则有问题
            if(node1 == null || node2 == null || node1.val != node2.val){
                return false;
            }
            queue1.offer(node1.left);
            queue2.offer(node2.right);
            queue1.offer(node1.right);
            queue2.offer(node2.left);
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

2018/2

from collections import deque

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        queue1 = deque()
        queue2 = deque()
        queue1.append(root.left)
        queue2.append(root.right)
        while queue1 and queue2:
            node1 = queue1.popleft()
            node2 = queue2.popleft()
            if node1 is None and node2 is None:
                continue
            if node1 is None or node2 is None:
                return False
            if node1.val != node2.val:
                return False
            queue1.append(node1.left)
            queue2.append(node2.right)
            queue1.append(node1.right)
            queue2.append(node2.left)
        return True

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/64541.html

相关文章

  • leetcode-101-Symmetric Tree-二叉对称问题

    摘要:解题思路所谓的对称,是左右相反位置的节点的值判断是否相同。只要出现不同,即可返回即可,否则继续进行处理。 topic: 101. Symmetric Tree Description: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For...

    seanlook 评论0 收藏0
  • 前端 | 每天一个 LeetCode

    摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...

    张汉庆 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月汇总(55 题攻略)

    摘要:微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...

    warmcheng 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<