Leetcode 面试题26. 树的子结构

问题描述

输入两棵二叉树A和B，判断B是不是A的子结构。（约定空树不是任意一棵树的子结构）
B是A的子结构，即A中有出现B相同的结构和节点值。

解题报告

B是A的子结构，存在三种情况：

• B的根节点和A的根节点相同，但是在分叉后，B首先停止；这种情况对应于helper()函数。
• B是A的左子树的子结构；这种情况对应于isSubStructure()函数。
• B是A的右子树的子结构；这种情况对应于isSubStructure()函数。

实现代码

/*** 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 isSubStructure(TreeNode* A, TreeNode* B) {if(A==NULL||B==NULL){return false;}if(B->val==A->val){return helper(A->left,B->left)&&helper(A->right, B->right);}else{return isSubStructure(A->left,B)||isSubStructure(A->right, B);}}bool helper(TreeNode* A, TreeNode* B){// 边界条件if(A==NULL||B==NULL){return B==NULL?true:false;}if(A->val==B->val){return helper(A->left,B->left)&&helper(A->right, B->right);}else{return false;}return true;}
};

参考资料

[1] Leetcode 面试题26. 树的子结构

Leetcode 617. 合并二叉树

问题描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL的节点将直接作为新二叉树的节点。

解题报告

• 当两棵树的同一节点都不为空，我们才把它俩压入栈中；
• 当左边的树后续节点【与右边的树对应】为空时，直接将其后续指向右边的树的后续节点；
• 当左边的树后续节点【与右边的树对应】不为空时，且右边对应节点的后续为空时，不处理。

实现代码

非递归

/*** 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:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2;if (t2 == NULL) return t1;stack<TreeNode*>s;s.push(t1);s.push(t2);while (!s.empty()){TreeNode* s2 = s.top();s.pop();TreeNode* s1 = s.top();s.pop();s1->val = s1->val + s2->val;if (s1->left == NULL) s1->left = s2->left;else if (s1->left != NULL && s2->left != NULL){s.push(s1->left);s.push(s2->left);}if (s1->right == NULL) s1->right = s2->right;else if (s1->right != NULL && s2->right != NULL){s.push(s1->right);s.push(s2->right);}}return t1;}
};

递归

class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2){if(!t1)return t2;if(!t2)return t1; t1->val += t2->val;t1->left = mergeTrees(t1->left, t2->left);t1->right = mergeTrees(t1->right, t2->right);return t1;}
};

参考资料

[1] Leetcode 617. 合并二叉树

Leetcode 面试题28. 对称的二叉树

问题描述

请实现一个函数，用来判断一颗二叉树是不是对称的。如果一颗二叉树和它的镜像一样，那么它是对称的。
例如二叉树[1,2,2,3,4,4,3]是对称的。但是[1,2,2,null,3,null,3]不是对称的。

解题报告

递归判断 左右子树 是否对称。
左右子树 对称必须满足下面三个条件：

• 左子树根节点的值和右子树的根节点的值相等；
• 左子树的左子树和右子树的右子树对称；
• 左子树的右子树和右子树的左子树对称。

实现代码

非递归

class Solution{public:bool isSymmetric(TreeNode *root){TreeNode *left, *right;if(root==NULL) return true;queue<TreeNode*>q;q.push(root->left);q.push(root->right);while(!q.empty()){left=q.front();q.pop();right=q.front();q.pop();if(left==NULL&&right==NULL) continue;if(left==NULL||right==NULL) return false;if(left->val != right->val) return false;q.push(left->left);q.push(right->right);q.push(left->right);q.push(right->left);}return true;}
};

递归

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root!=NULL){return helper(root->left, root->right);}return true;}bool helper(TreeNode*left, TreeNode*right){if(left==NULL&&right==NULL) return true;if(left==NULL||right==NULL) return false;if(left->val != right->val) return false;return helper(left->left, right->right)&&helper(left->right,right->left);}
};

参考资料

[1] Leetcode 面试题28. 对称的二叉树
[2] 题解区：堂吉诃德与桑丘