列表

详情

1612. 检查两棵二叉表达式树是否等价

二叉表达式树是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。 叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符。在本题中，我们只考虑 '+' 运算符（即加法）。

给定两棵二叉表达式树的根节点 root1 和 root2 。如果两棵二叉表达式树等价，返回 true ，否则返回 false 。

当两棵二叉搜索树中的变量取任意值，分别求得的值都相等时，我们称这两棵二叉表达式树是等价的。

 

示例 1:

输入： root1 = [x], root2 = [x]
输出： true

示例 2:

输入：root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
输出：true
解释：a + (b + c) == (b + c) + a

示例 3:

输入： root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
输出： false
解释： a + (b + c) != (b + d) + a

 

提示：

 

进阶：当你的答案需同时支持 '-' 运算符（减法）时，你该如何修改你的答案

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * Definition for a binary tree node. * struct Node { * char val; * Node *left; * Node *right; * Node() : val(' '), left(nullptr), right(nullptr) {} * Node(char x) : val(x), left(nullptr), right(nullptr) {} * Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool checkEquivalence(Node* root1, Node* root2) { } };

java 解法, 执行用时: 5 ms, 内存消耗: 43.9 MB, 提交时间: 2023-10-20 19:33:12 

/**
 * Definition for a binary tree node.
 * class Node {
 *     char val;
 *     Node left;
 *     Node right;
 *     Node() {this.val = ' ';}
 *     Node(char val) { this.val = val; }
 *     Node(char val, Node left, Node right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
	public boolean checkEquivalence(Node root1, Node root2) {
		int[] list1 = new int[26];
		int[] list2 = new int[26];
		traval(root1, list1);
		traval(root2, list2);
		for(int i = 0;i<26;i++) {
			if(list1[i]!=list2[i]) {
				return false;
			}
		}
		
		return true;
    }
	
	private void traval(Node root,int[] list) {
		if(root==null) {
			return;
		}
		if(root.val != '+') {
			list[root.val-'a']++;
		}
		traval(root.left, list);
		traval(root.right, list);
	}
}

cpp 解法, 执行用时: 992 ms, 内存消耗: 354.1 MB, 提交时间: 2023-10-20 19:32:16 

/**
 * Definition for a binary tree node.
 * struct Node {
 *     char val;
 *     Node *left;
 *     Node *right;
 *     Node() : val(' '), left(nullptr), right(nullptr) {}
 *     Node(char x) : val(x), left(nullptr), right(nullptr) {}
 *     Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checkEquivalence(Node* root1, Node* root2) {
        return dfs(root1) == dfs(root2);
    }
    ////////// 统计树rt各个字母的个数 //////////
    unordered_map<char, int> dfs(Node * rt) {
        unordered_map<char, int> res;
        //// 空结点
        if (rt == NULL)
            return res;
        //// 叶结点
        if (rt->left==NULL && rt->right==NULL) {
            res[rt->val] = 1;
            return res;
        }
        //// 其他情况
        auto L = dfs(rt->left);
        auto R = dfs(rt->right);
        for (auto [c, cnt] : L)
            res[c] += cnt;
        for (auto [c, cnt] : R)
            res[c] += cnt;
        return res;
    }
};

cpp 解法, 执行用时: 368 ms, 内存消耗: 187.4 MB, 提交时间: 2023-10-20 19:31:47 

/**
 * Definition for a binary tree node.
 * struct Node {
 *     char val;
 *     Node *left;
 *     Node *right;
 *     Node() : val(' '), left(nullptr), right(nullptr) {}
 *     Node(char x) : val(x), left(nullptr), right(nullptr) {}
 *     Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool checkEquivalence(Node* root1, Node* root2) {
        return dfs(root1) == dfs(root2);
    }
    ////////// 统计树rt各个字母的个数 //////////
    vector<int> dfs(Node * rt) {
        vector<int> res(26, 0);
        //// 空结点
        if (rt == NULL)
            return res;
        //// 叶结点
        if (rt->left==NULL && rt->right==NULL) {
            res[rt->val - 'a'] = 1;
            return res;
        }
        //// 其他情况
        vector<int> L = dfs(rt->left);
        vector<int> R = dfs(rt->right);
        for (int i = 0; i < 26; i ++)
            res[i] = L[i] + R[i];
        return res;
    }
};

python3 解法, 执行用时: 688 ms, 内存消耗: 19 MB, 提交时间: 2023-10-20 19:31:12 

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=" ", left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
        return self.dfs(root1) == self.dfs(root2)   

    #### 统计树rt各个字母的个数
    def dfs(self, rt: 'Node') -> dict():
        ## 空结点
        res = defaultdict(int)
        if rt == None:
            return res
        ## 叶结点
        if rt.left == None and rt.right == None:
            res[rt.val] = 1
            return res
        ## 非叶结点
        L = self.dfs(rt.left)
        R = self.dfs(rt.right)
        for char,cnt in L.items():
            res[char] += cnt
        for char,cnt in R.items():
            res[char] += cnt
        return res

python3 解法, 执行用时: 868 ms, 内存消耗: 18.9 MB, 提交时间: 2023-10-20 19:30:54 

# Definition for a binary tree node.
# class Node(object):
#     def __init__(self, val=" ", left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:
        return self.dfs(root1) == self.dfs(root2)   

    #### 统计树rt各个字母的个数
    def dfs(self, rt: 'Node') -> List[int]:
        ## 空结点
        if rt == None:
            return [0 for _ in range(26)]
        ## 叶结点
        if rt.left == None and rt.right == None:
            res = [0 for _ in range(26)]
            idx = ord(rt.val) - ord('a')
            res[idx] = 1
            return res
        ## 非叶结点
        L = self.dfs(rt.left)
        R = self.dfs(rt.right)
        return [ L[i]+R[i] for i in range(26)]

上一题

© 2024 leetcode.cn