leetcode Binary Tree

leetcode 100题

Posted by franki on November 16, 2020

leetcode 100题 相同的树

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

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

示例

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

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

输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

利用深度优先遍历，依次比较根节点，接着左右节点，递归比较，最终确定两棵树是否相等

注意：

  • 终止条件，如果遍历结束，p q 同为null，则是相同的树
  • 当 p q 都不为空，且 p 的 val、q 的 val 都相等时，则需要继续比较两者的左右节点，知道递归结束
  • 当 p、q 两者有其一为空，或者 p、q 都不为空，值不等时，直接返回false

代码

function isSameTree(p, q) {
    if (p === null && q === null) {
        return true;
    }

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

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS