azl397985856 commented 3 years ago

100. 相同的树

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/same-tree/

前置知识

递归
层序遍历

前中序确定一棵树

题目描述


给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入: 1 1 / \ / \ 2 3 2 3

    [1,2,3],   [1,2,3]

输出: true 示例 2:

输入: 1 1 / \ 2 2

    [1,2],     [1,null,2]

输出: false 示例 3:

输入: 1 1 / \ / \ 2 1 1 2

    [1,2,1],   [1,1,2]

输出: false

15691894985 commented 3 years ago

day14 9.23 100. 相同的树

https://leetcode-cn.com/problems/same-tree/

方法一：递归递归三要素：出口，调用解决更小的问题，调用的父问题和子问题没有交集

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        #        分解子问题，判断左树是否相同，右边树是否相同
        if not p and not q:
            return True
        if not p or not q:
            return False
        # 返回相同节点，然后判断左右子树的情况
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

复杂度分析：

时间复杂度：O(N),其中N为树的节点
空间复杂度：O(h)，递归调的次数就是最大的树高度

方法二：广度优先搜索

思路：

判断每层树的内容是否相同，通过队列实现
首先判空，用两个队列存储两个二叉树的节点
两个节点值相同，判断子树结构是否相同，子节点的值是否为空，若存在一个节点值为空，另一个不为空，则False

如果两个节点的结构相同，将两个节点的非空节点分别加入两个队列，若左右节点都不为空时候，先加左节点，再右节点

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    q1 = collections.deque([p])
    q2 = collections.deque([q])
    # 取队头元素比较是否一致
    while q1 and q2:
        node1 = q1.popleft() #移除最左侧元素
        node2 = q2.popleft()
        if node1.val != node2.val:
            return False
        # 把树通过层次遍历放进队列
        left1, right1 = node1.left, node1.right
        left2, right2 = node2.left, node2.right
        if (not left1) ^ (not left2):  #存在值的时候返回Falase 因为异或操作，存在值则说明两个不相等
            return False
        if (not right1) ^ (not right2):  #存在值的时候返回Falase 因为异或操作，存在值则说明两个不相等
            return False
        if left1:
            q1.append(left1)
        if right1:
             q1.append(right1)
        if left2:
            q2.append(left2)
        if right2:
             q2.append(right2)
     return True

复杂度分析：

时间复杂度：O(min(m,n)) 对两颗树进行遍历，访问不会超过最小的那颗二叉树
空间复杂度：O(min(m,n)) 队列存储的节点空间

aatoe commented 3 years ago

dfs 递归两颗树，然后进行对比，然后对null处理。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if( p === null && q === null) return true
    else if( !p || !q) return false
    return dfs(p,q)

    function dfs(treeA,treeB){
        // 处理为null的情况
        // [2], null
        // null,null
        if (!treeA || !treeB) {
            return !treeA && !treeB;
        }

        // 值相等，递归左右子树
        if(  treeA.val === treeB.val ){
            let flagLeft = dfs(treeA.left,treeB.left)
            let flagRight = dfs(treeA.right,treeB.right)
            return flagLeft && flagRight
        }else{
            return false
        }
    }
};

var isSameTree = function(treeA, treeB) {
        // 处理为null的情况
        // [2], null
        // null,null
        if (!treeA || !treeB) {
            return !treeA && !treeB;
        }

        // 值相等，递归左右子树
        if(  treeA.val === treeB.val ){
            let flagLeft = isSameTree(treeA.left,treeB.left)
            let flagRight = isSameTree(treeA.right,treeB.right)
            return flagLeft && flagRight
        }else{
            return false
        }
};

时间复杂度为 O(N) N为树的节点数，因为递归到了每一个节点所以为O(N)
空间复杂度为 O(h) h为树的高度，也就是递归的层数。

ningli12 commented 3 years ago

思路

Recursion

代码

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

复杂度

时间复杂度: O(N)
空间复杂度: O(h)

biancaone commented 3 years ago

思路 🏷️

递归

代码 📜

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True

        if not p or not q:
            return False

        if p.val != q.val:
            return False

        left = self.isSameTree(p.left, q.left)
        right = self.isSameTree(p.right, q.right)

        if left and right:
            return True 
        return False

复杂度 📦

时间复杂度 O(n)
空间复杂度O(1)

lxy030988 commented 3 years ago

思路

深度优先递归
3 个终止条件: 1.两个节点都是 null 说明相同
2.一个节点是 null,另一个节点不是 null, 说明不相同
3.节点的两个值不相等,说明不相同

代码 js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  if (q == null && p == null) {
    return true
  }
  if (p == null || q == null) {
    return false
  }
  if (p.val != q.val) {
    return false
  }
  return isSameTree(q.left, p.left) && isSameTree(q.right, p.right)
}

复杂度分析

时间复杂度：O(n) p 和 q 两个节点数小的那个
空间复杂度：O(height) p 和 q 两个节点高度低的那个

ff1234-debug commented 3 years ago

思路

深度优先遍历,首先判空,如果都为空,返回true.如果一个为空一个不为空, 返回false.再判断值是否相同,如果不同返回false,如果相同则递归判断两个节点的左子树和右子树是否相同.

代码 C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
         if(p==nullptr&&q==nullptr) return true;
         else if(p==nullptr||q==nullptr) return false;
         else if(p->val!=q->val) return false;
         else return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

复杂度分析

m, n 为两颗树的节点数目
时间复杂度：O(min(m,n))
空间复杂度：O(min(m,n))

Toms-BigData commented 3 years ago

【Day 14】100. 相同的树

思路

前序遍历两棵树都相同返回true否则返回false

代码

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> 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)

复杂度

时间:O(n) 空间:O(n)

littlemoon-zh commented 3 years ago

day 14

100. Same Tree

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

carsonlin9996 commented 3 years ago

两个node 都是 null的情况下 = true
其中一个node 是null的情况下 = false
node.val 值不符， = false

左右递归

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

    boolean left = isSameTree(p.left, q.left);
    boolean right = isSameTree(p.right, q.right);

    return left && right;

}
}

jsu-arch commented 3 years ago

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # p and q are both None
        if not p and not q:
            return True
        # either p or q is not None
        if not q or not p:
            return False
        # root node is not the same
        if q.val != p.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)


O(n). We need to go through all the nodes 

``` Space Complexity
O(h)

maxyzli commented 3 years ago

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  if (q == null && p == null) {
    return true
  }
  if (p == null || q == null) {
    return false
  }
  if (p.val != q.val) {
    return false
  }
  return isSameTree(q.left, p.left) && isSameTree(q.right, p.right)
}

pangjiadai commented 3 years ago

思路：递归

Python3

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if not p or not q: return False
        if p.val != q.val: return False

        if self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) is True:
            return True
        else:
            return False

Zz10044 commented 3 years ago

/**

Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
} */ /**
@param {TreeNode} p
@param {TreeNode} q
@return {boolean} */ var isSameTree = function (p, q) { if (q == null && p == null) { return true } if (p == null || q == null) { return false } if (p.val != q.val) { return false } return isSameTree(q.left, p.left) && isSameTree(q.right, p.right) }

carterrr commented 3 years ago

class 相同的树_100 { public boolean isSameTree(TreeNode p, TreeNode q) { // dfs if(p == null|| q == null) return (p == null) == (q == null); // 空属性相同 if(p!= null && q != null && p.val != q.val) return false; // 非空值不等 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 其他条件 } }

watermelonDrip commented 3 years ago

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p and q:
            return False
        if not q and p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

时间复杂度：每个节点至多访问一次O(N) 空间复杂度：跟tree 的深度一样O(h)

weichuliao commented 3 years ago

Main Idea

DFS and recursion
BFS and queue
Preorder and inorder traversal decide a tree

Code with Python

Solution I

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Solution II

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True
        if not p or not q: return False
        if p.val != q.val: return False

        q1 = deque()
        q2 = deque()
        q1.append(p)
        q2.append(q)

        while q1 and q2:
            node1 = q1.popleft()
            node2 = q2.popleft()

            if node1.val != node2.val: return False

            left1, left2 = node1.left, node2.left
            right1, right2 = node1.right, node2.right

            if (not left1) ^ (not left2): return False
            if (not right1) ^ (not right2): return False

            if left1: q1.append(left1)
            if left2: q2.append(left2)
            if right1: q1.append(right1)
            if right2: q2.append(right2)

        return not q1 and not q2

Solution III

class Solution:
    def preorder(self, root, arr):
        if not root: 
            arr.append(" ")
            return arr

        arr.append(root.val)
        self.preorder(root.left, arr)
        self.preorder(root.right, arr)
        return arr

    def inorder(self, root, arr):
        if not root:
            arr.append(" ")
            return arr

        self.inorder(root.left, arr)
        arr.append(root.val)
        self.inorder(root.right, arr)
        return arr

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        pre1 = []
        pre1 = self.preorder(p, pre1)
        in1 = []
        in1 = self.inorder(p, in1)

        pre2 = []
        pre2 = self.preorder(q, pre2)
        in2 = []
        in2 = self.inorder(q, in2)

        return (pre1 == pre2) and (in1 == in2)

Complexity Analysis

Solution I

Time: O(N), where N denotes the number of nodes
Space: O(h), where h denotes the height of the tree
Solution II
Time: O(N), where N denotes the number of nodes
Space: O(Q), where Q denotes the maximum length of the queue
Solution III
Time: O(N), where N denotes the number of nodes
Space: O(N), where N denotes the number of nodes

itsjacob commented 3 years ago

Intuition

The trees are same if and only if the current node values equal, left subtrees are the same and right subtrees are the same. This naturally gives the recursive solution
The base case is to check if either p or q is null nodes

Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
  bool isSameTree(TreeNode *p, TreeNode *q)
  {
    if (p == nullptr && q == nullptr) return true;
    if (p != nullptr && q == nullptr) return false;
    if (p == nullptr && q != nullptr) return false;
    bool res{ true };
    res &= (p->val == q->val);
    res &= isSameTree(p->left, q->left);
    res &= isSameTree(p->right, q->right);
    return res;
  }
};

Complexity

Time complexity: O(n) for traversing the tree
Space complexity: O(h), h is the height of the tree

leolisgit commented 3 years ago

思路

前序遍历，对比每一个节点。

代码

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;

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

复杂度

时间：O(n)
空间：O(h)

shuichen17 commented 3 years ago

/*
Time complexity: O(N)
Space complexity: O(h)
*/
var isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val === q.val) {
       return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    } else {
        return false;
    }
};

suukii commented 3 years ago

Link to LeetCode Problem

S1: DFS

因为二叉树的子树也是一个二叉树，所以很适合使用递归的方式来解决。

用《产品经理法》来解决递归问题。

定义函数功能，先不用管其具体实现。

我们需要一个函数，给定两个二叉树的根节点，返回这两个二叉树是否相同的判断结果。假设我们已经有这个函数 F，那问题就转化为 F(root1, root2) 了。
确定大问题和小问题的关系。

要解决 F(root1, root2)，明显需要先解决的问题是：
- F(root1.left, root2.left)
- F(root1.right, root2.right)
而它们之间的关系也是显而易见的，两个二叉树要相等的话，当然其根节点和左右子节点都要相等，所以：

F(root1, root2) = root1 === root2 && F(root1.left, root2.left) && F(root1.right, root2.right)
补充递归终止条件
- p, q 都是 null 的时候返回 true
- p, q 只有一个是 null 的时候返回 false
- p, q 值不相同的话返回 false

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    if (!p && !q) return true;
    if (!p || !q || p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    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
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time: $O(N)$，N 是二叉树的节点总数。
Space: $O(logN)$

S2: BFS

前置：二叉树的层级遍历

对两个二叉树同时进行层级遍历，在遍历过程中逐一比较节点即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) return true;
        if (p == nullptr || q == nullptr) return false;

        queue<TreeNode*> qp; qp.push(p);
        queue<TreeNode*> qq; qq.push(q);

        while (!qp.empty() && !qq.empty()) {
            int sizeP = qp.size();
            int sizeQ = qq.size();
            if (sizeP != sizeQ) return false;
            while (sizeP--) {
                TreeNode* nodeP = qp.front(); qp.pop();
                TreeNode* nodeQ = qq.front(); qq.pop();

                if (nodeP == nullptr && nodeQ == nullptr) continue;
                if (nodeP == nullptr || nodeQ == nullptr) return false;
                if (nodeP->val != nodeQ->val) return false;

                qp.push(nodeP->left); qp.push(nodeP->right);
                qq.push(nodeQ->left); qq.push(nodeQ->right);
            }
        }

        return qp.empty() && qq.empty();

    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    const queueP = [p];
    const queueQ = [q];

    while (queueP.length && queueQ.length) {
        let lenP = queueP.length;
        let lenQ = queueQ.length;

        // 如果两棵树同一层的节点数都不同，肯定不是同一棵树
        if (lenP !== lenQ) return false;

        while (lenP-- && lenQ--) {
            const nodeP = queueP.shift();
            const nodeQ = queueQ.shift();

            // 两个节点都是 null, 直接继续比较下一个节点
            if (!nodeP && !nodeQ) continue;
            // 遇到不同的节点，说明不是同一棵树，提前返回
            if (!nodeP || !nodeQ || nodeP.val !== nodeQ.val) return false;

            // 将下一层的节点入列，空节点也要入列
            queueP.push(nodeP.left, nodeP.right);
            queueQ.push(nodeQ.left, nodeQ.right);
        }
    }
    return true;
};

Time: $O(N)$，N 是二叉树的节点总数。
Space: $O(N)$

S3: 比较前序+中序遍历结果

前序+中序遍历结果可以确定一棵树，所以比较这两个遍历结果也可以判断出两个二叉树是否相同。要注意的是，遍历的时候给空节点也留个位置。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        vector<int> preorderListP, preorderListQ;
        preorder(p, preorderListP);
        preorder(q, preorderListQ);
        if (preorderListP != preorderListQ) return false;

        vector<int> inorderListP, inorderListQ;
        inorder(p, inorderListP);
        inorder(q, inorderListQ);
        return inorderListP == inorderListQ;
    }
    void preorder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            res.push_back('#');
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
    void inorder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            res.push_back('#');
            return;
        }
        preorder(root->left, res);
        res.push_back(root->val);
        preorder(root->right, res);
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    const preOrderP = preorderTraversal(p).join('');
    const preOrderQ = preorderTraversal(q).join('');

    const inOrderP = inorderTraversal(p).join('');
    const inOrderQ = inorderTraversal(q).join('');

    return preOrderP === preOrderQ && inOrderP === inOrderQ;
};

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root, res = []) {
    if (!root) {
        // 标记空节点
        res.push('#');
        return res;
    }

    res.push(root.val);
    preorderTraversal(root.left, res);
    preorderTraversal(root.right, res);

    return res;
};

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root, res = []) {
    if (!root) {
        // 标记空节点
        res.push('#');
        return res;
    }

    inorderTraversal(root.left, res);
    res.push(root.val);
    inorderTraversal(root.right, res);

    return res;
};

Time: $O(N)$，N 是二叉树的节点总数。
Space: $O(logN)$

cicihou commented 3 years ago


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        '''
        method 1 recursion
        time: O(N)
        space: O(logN)

        注意先判断 not p and not q 这个比较狭窄的条件，再判断 False 对应的比较宽的条件
        '''
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        '''
        method 2 iteration + queue

        time: O(N)
        space: O(logN)
        '''
        def same(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val != q.val:
                return False
            return True

        # FIFO via queue + breadth travel
        queue = [(p, q)]
        while queue:
            p, q = queue.pop(0)
            if not same(p, q):
                return False

            if p:
                queue.append((p.left, q.left))
                queue.append((p.right, q.right))
        return True

        '''
        method 3 some oneline solutions, cool!
        https://leetcode.com/problems/same-tree/discuss/32729/Shortest%2Bsimplest-Python
        '''

lihanchenyuhua commented 3 years ago

class Solution { public: bool isSameTree(TreeNode p, TreeNode q) { if (p == nullptr && q == nullptr) { return true; } else if (p == nullptr || q == nullptr) { return false; } else if (p->val != q->val) { return false; } else { return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } } };

linearindep commented 3 years ago

【思路】先判断两个都有没有node，有node在判断值一不一样。return 左边和右边的AND结果【复杂度】O(1)每个node都只遍历一遍

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null && q != null) return false;
        if(p != null && q == null) return false;
        if(p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }

ivalkshfoeif commented 3 years ago

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

    }
}

枚举写法，very understandable LOL

benngfour commented 3 years ago

思路

Set up base case, then recurse function to traverse the tree.

語言

JavaScript

Code Solution

var isSameTree = function(p, q) {
    if (!q && !p) return true;
    if (!q || !p) return false;
    if (q.val !== p.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

複雜度分析

時間複雜度 O(N): Tree Depth
空間複雜度 O(N): function recursion

QiZhongdd commented 3 years ago

递归判断左右节点是否相同

时间复杂度：O(n),空间复杂度O(n)

newbeenoob commented 3 years ago

思路

DFS / BFS 思路详见代码注释

代码：JavaScript

递归：

var isSameTree = function(p, q) {
    // 由于是先序遍历 到这里代表两颗树都已经走完 则 返回 true
    if (!p && !q) return true; 
    // 如果当前一棵子树为空 一棵不为空 返回 false
    if (( p || q ) && !(p && q)) return false; 
    // 继续比较两棵非空子树 值不等 也返回 false
    if (p.val !== q.val) return false; 
    // 最后递归比较左右子树
    return isSameTree(p.left , q.left) && isSameTree(p.right , q.right);
};

非递归：（BFS）

// 一层一层比较两棵树的节点，设置两个辅助队列分别存储两棵树的层序节点 同步地进行出入队操作
var isSameTree = function(p, q) {
    const qa = [];
    const qb = [];

    qa.push(p);
    qb.push(q);
    let ea , eb;

    while(qa.length && qb.length) {

        let sz = qa.length;
        for(let _ = 0 ; _ < sz ; ++_) {
            // 同步地出队
            ea = qa.shift();
            eb = qb.shift();
            if (!ea && !eb) continue;
            // 有一节点为空 另一节点非空 返回 false
            if (!(ea && eb) && (ea || eb)) return false;
            // 值不等 返回 false
            if (ea.val !== eb.val) return false;
            // 同步地将左右子树按顺序入队
            qa.push(ea.left);
            qa.push(ea.right);
            qb.push(eb.left);
            qb.push(eb.right);
        }
    }

    // 最后比较两个辅助队列当中的存储元素个数 如果两棵树结构一致 遍历完成后一定有
    // qa.length === qb.length === 0
    return qa.length === qb.length;
};

复杂度分析

递归版：

时间复杂度： O(n)
额外空间复杂度： O(h) 其中 h 为树高 ~ lgn n 为树中节点

非递归版：

时间复杂度： o(n)
额外空间复杂度: o(n)

Day 14 100. Same Tree (binary tree, BFS, tree traversals)

Problem Link
- 100. Same Tree
Ideas
- it is an easy problem. We just focus on the basic structure, focus on one root and its left and right node and use recursion to solve the problem. If the value is not same or one of the the node is null while the other is not, return False
Complexity:
- Time: O(# nodes)
- Space: O(depth of the tree)
Code

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

other resources:

siyuelee commented 3 years ago

先用递归，bfs周末看了讲义再补。。如果root本身相等并且左子树和右子树相等，则两数相等

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

O(# of nodes) O(depth of tree)

muimi commented 3 years ago

思路

使用递归，需要注意null的判断和检查

代码

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(1)，没有使用额外的存储空间

cassiechris commented 3 years ago

思路

递归

代码

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

复杂度分析

时间复杂度: $O(N)$，N为节点数
空间复杂度: $O(h)$，h为树的高度

SunnyYuJF commented 3 years ago

思路

Recursion

代码 Python

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        elif not p and q:
            return False
        elif not q and p:
            return False
        elif p.val!=q.val:
            return False

        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

复杂度分析

时间复杂度： O(N)
空间复杂度： O(H) H is the depth of the tree

hwpanda commented 3 years ago

时间复杂度：O(n) 空间复杂度：O(h)

const isSameTree = (p, q) => {
  if(p === null && q === null){
      return true;
  }
  if(p === null || q === null){
      return false;
  }
  if(p.val !== q.val){
      return false;
  }

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

taojin1992 commented 3 years ago

Method 1: recursion

time: O(n), n = number of nodes
space: O(height), O(logn) on average, O(n) for degenerate trees

Method 2: level-order

1 queue, compare the level
借助队列实现层次遍历，并在每次取队头元素的时候比较两棵树的队头元素是否一致。如果不一致，直接返回 false。如果访问完都没有发现不一致就返回 true。

null也放入queue, add "if (n1 == null && n2 == null) continue;// important!"

time: O(n), n = number of nodes
space: O(Q), widest level of nodes, bounded by O((n+1)/2), O(n)

[1,2]
[1,null,2] -> false

Method 3:

前序和中序的遍历结果确定一棵树，那么当两棵树前序遍历和中序遍历结果都相同，那是否说明两棵树也相同。

time: O(n), n = number of nodes
space: O(height), O(logn) on average, O(n) for degenerate trees + list O(n)

Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

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

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
            TreeNode n1 = queue.poll();
            TreeNode n2 = queue.poll();

            if (n1 == null && n2 == null) continue;// important!
            if (n1 == null || n2 == null)  {
                return false;
            }
            if (n1.val != n2.val) {
                return false;
            }
            queue.offer(n1.left);
            queue.offer(n2.left);

            queue.offer(n1.right);
            queue.offer(n2.right);
        }
        return true;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        List<Integer> preP = new ArrayList<>();
        List<Integer> inP = new ArrayList<>();
        List<Integer> preQ = new ArrayList<>();
        List<Integer> inQ = new ArrayList<>();

        preorder(p, preP);
        preorder(q, preQ);
        inorder(p, inP);
        inorder(q, inQ);

        // System.out.println(preP+""); // [1, 2, null, null, null]
        return (preP+"").equals(preQ + "") && (inP+"").equals(inQ + "");

    }

    private void preorder(TreeNode root, List<Integer> traversal) {
        if (root == null) {
            traversal.add(null);
            return;
        }
        traversal.add(root.val);
        preorder(root.left, traversal);
        preorder(root.right, traversal);
    }

    private void inorder(TreeNode root, List<Integer> traversal) {
        if (root == null) {
            traversal.add(null);
            return;
        } 
        inorder(root.left, traversal);
        traversal.add(root.val);
        inorder(root.right, traversal);
    }

}

ZJP1483469269 commented 3 years ago

思路

递归

代码

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

    }

}
}

复杂度分析

时间复杂度：O（N）空间复杂度：O（H）

Socrates2001 commented 3 years ago

时间：2021年9月23日13:41:36
题目：100. 相同的树
思路：若两根节点都为空，两棵树当然相同；若其中有一个为空，则不相同；若都不为空，

则检测两节点的值，不等则不同，相等则递归判断其左子树和右子树是否同时相同。

C implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

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

}

时间复杂度：O(n)，其中n为节点数最少的树的节点数
空间复杂度：O(1)

LareinaWei commented 3 years ago

Thinking

Using DFS. Recursively checking if the left and right subtree is the same.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        elif not p or not q:
            return False
        else:
            if p.val != q.val:
                return False
            else:
                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity

Time complexity: O(n). Space complexity: O(h)

Abby-xu commented 3 years ago

思路

BFS + Queue

代码（Python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue = [(p, q)]
        while queue:
            node1, node2 = queue.pop(0)
            if not node1 and not node2: # no child
                continue
            elif None in [node1, node2]:
                return False
            else:
                if node1.val != node2.val:
                    return False
                queue.append((node1.left, node2.left))
                queue.append((node1.right, node2.right))
        return True

Complexity

Time: O(n) Space: O(h)

q815101630 commented 3 years ago

前序遍历，通过 and 链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, nodeP: TreeNode, nodeQ: TreeNode) -> bool:
        if not nodeP and not nodeQ:
            return True
        elif not nodeP and nodeQ:
            return False
        elif nodeP and not nodeQ:
            return False
        elif nodeP.val != nodeQ.val:
            return False

        return (nodeP.val == nodeQ.val) and self.isSameTree(nodeP.left, nodeQ.left) and self.isSameTree(nodeP.right, nodeQ.right)

时间 O(n) 空间 O(n)

Huangxuang commented 3 years ago

题目：100. Same Tree

思路

返回给上层什么：当前层Node以前是否相等；传递给下一层什么：左右节点即可
从下一层拿到什么：左右节点以前是否相等；当前层做什么：决策是否当前Node以前是否相等

代码

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        //both q and p are not null 
        boolean leftIsSame = isSameTree(p.left, q.left);
        boolean rightIsSame = isSameTree(p.right, q.right);

        return leftIsSame && rightIsSame && q.val == p.val;

    }
}

复杂度分析

时间复杂度： n个node，2个数，2O(n)
空间复杂度：递归数的detp次，最多n层

yanjyumoso commented 3 years ago

DFS

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not p and q:
            return False
        elif not q and p:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) if p.val == q.val else False

Time: O(n)
Space: O(n)

ZhuMengCheng commented 3 years ago

思路: 深度优先查找,对比父节点信息是否一致,不同false,在对比每一个字节点,如果不同返回false


var isSameTree = function(p, q) {
    if(p == null && q == null){
        return true;
    }else if(p == null || q == null){
        return false;
    }else if(p.val != q.val){
        return false
    }else{
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
};

时间复杂度:O(M||N) 空间复杂度:O(M||N)

Bochengwan commented 3 years ago

思路

DFS

代码

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val!=q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(N)

zhiyuanpeng commented 3 years ago

class Solution:

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

        if not p and q:
            return False
        if p and not q:
            return False
        if not p and not q:
            return True
        else:
            l = self.isSameTree(p.left, q.left)
            r = self.isSameTree(p.right, q.right)
        return l&r&(p.val==q.val)

time O(n) space O(logn)

RonghuanYou commented 3 years ago

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None and q == None:
            return True

        if p != None and q != None:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

        return False

kennyxcao commented 3 years ago

100. Same Tree

Intuition

DFS
- check each node of p with the matching node of q
- return false if any pair of node has mismatch

Code

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
const isSameTree = function(p, q) {
  if (!p && !q) return true; // both null
  if (!p || !q) return false; // only one is null
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

Complexity Analysis

Time: O(n)
Space: O(h)
n = total num of nodes
h = max height of the tree

freesan44 commented 3 years ago

思路

采用递归的方式来监测

代码

语言支持：Python3

Python3 Code:


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        leftRes = self.isSameTree(p.left,q.left)
        rightRes = self.isSameTree(p.right, q.right)
        if p.val == q.val and leftRes and rightRes:
            return True
        else:
            return False

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(logn)$

HouHao1998 commented 3 years ago

思想

递归，判断树顶的值是否相同，然后左树和右树是否相同，都相同则返回true、

代码

class Solution {

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

    }
}

复杂度

T：O（n） S：O（N）

ZoharZhu commented 3 years ago

思路

https://leetcode-cn.com/problems/same-tree/solution/hua-jie-suan-fa-100-xiang-tong-de-shu-by-guanpengc/

代码

var isSameTree = function(p, q) {
    if(p == null && q == null) {
        return true
    }
    if (p == null || q == null) {
        return false
    }
    if (p.val != q.val) {
        return false
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

复杂度

时间复杂度：<O(n)>
空间复杂度：<O(n)>

HondryTravis commented 3 years ago

思路

深度递归比较

left 比 left ，right 比 right

代码

var isSameTree = function(p, q) {

  // 如果当前两个节点都为 null 那肯定是相同的
  if (p === null && q === null) return true
  // 如果两个节点中有一个为 null 或者值不相等，也不相等
  if (p === null || q === null || (p.val !== q.val)) return false

  // 两颗树同时比较left 和 right
  return isSameTree(p.left, q.left)
      && isSameTree(p.right, q.right)
};

复杂度分析

时间复杂度：O(min(p,q)) 空间复杂度：O(min(p,q))

leetcode-pp / 91alg-5-daily-check

【Day 14 】2021-09-23 - 100. 相同的树 #29

100. 相同的树

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度

思路 🏷️

代码 📜

复杂度 📦

思路

代码 js

复杂度分析

思路

代码 C++

【Day 14】100. 相同的树

思路

代码

复杂度

day 14

思路： 递归

Python3

Main Idea

Code with Python

Solution I

Solution II

Solution III

Complexity Analysis

Solution I

Solution II

Solution III

Intuition

Implementation

Complexity

思路

代码

复杂度

S1: DFS

S2: BFS

S3: 比较前序+中序遍历结果

思路

語言

Code Solution

複雜度分析

思路

代码：JavaScript

复杂度分析

标签

Day 14 100. Same Tree (binary tree, BFS, tree traversals)

思路

代码

复杂度

思路

代码

思路

代码 Python

复杂度分析

Method 1: recursion

Method 2: level-order

Method 3:

Code:

思路

代码

复杂度分析

C implementation

Thinking

Code

Complexity

思路

代码 （Python）

Complexity

题目：100. Same Tree

思路

代码

复杂度分析

思路

代码

思路：递归

代码（Python）