100. 相同的树

逃离我推掉我的手 2023-02-18 09:41 65阅读 0赞

# 题目来源 #

[100. 相同的树][100.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

先序遍历的递归形式

/**
     * 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){
        
                return false;
            }
            
            if (q == null){
        
                return false;
            }
            
            if (q.val != p.val){
        
                return false;
            }
            
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

![在这里插入图片描述][20200617092136724.png]

## 队列–层次遍历 ##

public boolean isSameTree(TreeNode p, TreeNode q) {
        
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(p);
            queue.offer(q);
    
            while (!queue.isEmpty()){
        
                TreeNode p1 = queue.pop();
                TreeNode p2 = queue.pop();
                if (p1 == null && p2 == null){
        
                    continue;  //易错点 [12 null 69] [12 null 11]
                }
    
                if (p1 == null || p2 == null){
        
                    return false;
                }
    
                if (p1.val != p2.val){
        
                    return false;
                }
    
                queue.offer(p1.left);
                queue.offer(p2.left);
                queue.offer(p1.right);
                queue.offer(p2.right);
            }
    
            return true;
        }

![在这里插入图片描述][20200617093444148.png]

[100.]: https://leetcode-cn.com/problems/same-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617093526107.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200617092136724.png]: https://img-blog.csdnimg.cn/20200617092136724.png
[20200617093444148.png]: https://img-blog.csdnimg.cn/20200617093444148.png