Skip to content

same-tree.md

Latest commit

 

History

History
217 lines (166 loc) · 5.98 KB

same-tree.md

File metadata and controls

217 lines (166 loc) · 5.98 KB

100. Same Tree - 相同的树

Tags - 题目标签

Description - 题目描述

EN:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

 

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104

ZH-CN:

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

 

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

 

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
javascript 52 ms 10.5 MB 2018/12/08 19:21 
/**
 * 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) {
    if (!p&&!q) {
        return true;
    } else if (!p&&q || !q&&p) {
        return false;
    }
    
    return (p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
    
};

My Notes - 我的笔记

100 相同的树

方法1 非递归

  • 二叉树的非递归前序遍历
    • 根节点p不为空，打印，根节点入栈，并将左孩子作为当前节点，左孩子即当前节点不为空，打印。一个while搞定
    • 若左孩子为空，跳出while循环；if stack 不为空，top栈顶作为当前节点，pop栈顶，将当前节点的右孩子作为当前节点
/**
 * 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) {
    var cur1 = p, cur2 = q,
        stack1 = [], stack2 = [];
    // console.log(stack1.length);
    while ((cur1 || stack1.length !== 0) || (cur2 || stack2.length !== 0)) {
         if (!cur1 && !cur2 && stack1.length === stack2.length === 0) {
            return true;
        }
        
        while (cur1 || cur2) {
            if ((!cur1&&cur2) || (cur1&&!cur2)) {
                return false;
            }
            if (cur1.val === cur2.val) {
                stack1.push(cur1);
                stack2.push(cur2);
                cur1 = cur1.left;
                cur2 = cur2.left;
            } else {
                return false;
            }
        }
        
        if (stack1.length !== 0 || stack2.length !== 0) {
            if (stack1.length !== 0 && stack2.length !== 0) {
                cur1 = stack1.pop();
                cur2 = stack2.pop();
                cur1 = cur1.right;
                cur2 = cur2.right;
            } else if ((stack1.length === 0 && stack2.length !== 0) ||
                       (stack1.length !== 0 && stack2.length === 0)) {
                return false;
            }
        }
    }
    return true;
}

方法2 递归

/**
 * 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) {
    if (!p&&!q) {
        return true;
    } else if (!p&&q || !q&&p) {
        return false;
    }
   
    return (p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)); //递归的返回值可以看作普通函数的返回值调用
    
};