[LeetCode] 100. Same Tree

轉自LeetCode

Given two binary trees, write a function to check if they are equal or not.

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

<Solution>

這題是要比較兩個 binary tree 是否一樣

可以用 DFS 來解這道題目，想法如下

• 兩個 node 都是 NULL 的時候，回傳 true

• 只有一個有值，或是兩個的值不一樣，就回傳 false

• 比完當前的值，檢查左子樹和右子樹是不是也一樣

code 如下
c++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSameTree(TreeNode* p, TreeNode* 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);
	}
	};

view raw checkSameBinaryTree_1.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
	return when {
	p == null && q == null -> true
	p == null || q == null -> false
	p!!.`val` != q!!.`val` -> false
	else -> {
	isSameTree(p!!.left, q!!.left) && isSameTree(p!!.right, q!!.right)
	}
	}
	}
	}

view raw same_tree.kt hosted with ❤ by GitHub

這題還可以用 binary tree traversal 的方式去解，有 inorder、preorder、postorder 可以選

在 traverse 的同時，檢查值和樹的結構是否一樣即可

這邊使用 preorder traversal 的方式，code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isSameTree(TreeNode* p, TreeNode* q) {
	stack<TreeNode *> nodeStack_1, nodeStack_2;
	//> use preorder binary tree traversal
	if(p) {
	nodeStack_1.push(p);
	}
	if(q) {
	nodeStack_2.push(q);
	}
	while(!nodeStack_1.empty() && !nodeStack_2.empty()) {
	TreeNode *tmpNode_1 = nodeStack_1.top();
	TreeNode *tmpNode_2 = nodeStack_2.top();
	nodeStack_1.pop();
	nodeStack_2.pop();
	//> check val
	if(tmpNode_1->val != tmpNode_2->val) {
	return false;
	}
	//> check structure
	if(tmpNode_1->right) {
	nodeStack_1.push(tmpNode_1->right);
	}
	if(tmpNode_2->right) {
	nodeStack_2.push(tmpNode_2->right);
	}
	if(nodeStack_1.size() != nodeStack_2.size()) {
	return false;
	}
	if(tmpNode_1->left) {
	nodeStack_1.push(tmpNode_1->left);
	}
	if(tmpNode_2->left) {
	nodeStack_2.push(tmpNode_2->left);
	}
	if(nodeStack_1.size() != nodeStack_2.size()) {
	return false;
	}
	}
	return nodeStack_1.size() == nodeStack_2.size();
	}
	};

view raw checkSameBinaryTree_2.cpp hosted with ❤ by GitHub