二叉树的题目都有两种解法，一种递归法，一般配合着回溯，一种迭代法，配合着栈和队列

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3

递归法思路：比较两个子树是否相同，子树的比较分为内侧和外侧，结果相于

bool isSymmetric(TreeNode* root){ if(root==NULL) return true; return compare(root->left,root->right); } bool compare(TreeNode* left,TreeNode* right){ if(left==NULL&&right==NULL)return true; else if(left==NULL&&right!=NULL) return false; else if(left!=NULL&&right==NULL) return false; else if(left->val!=right->val) return false; bool outside=compare(left->left,right->right); bool insisde=compare(left->right,right->left); return outside&&inside; }

迭代思路：用两个栈或者队列左子树左右中，右子树右左中来比较

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

本来想用两个队列来实现，后来发现一个即可，用栈也可以写。

572. 另一个树的子树

和上一题相似

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 示例 1: 给定的树 s: 3 / \ 4 5 / \ 1 2 给定的树 t： 4 / \ 1 2 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。 示例 2: 给定的树 s： 3 / \ 4 5 / \ 1 2 / 0 给定的树 t： 4 / \ 1 2 返回 false。

思路：遍历S子树，然后比较是否相同，相同就继续，不同就换一个结点

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSubtree(TreeNode* s, TreeNode* t) {//递归 queue<TreeNode*> que; que.push(s); while(!que.empty()){ int size=que.size(); for(int i=0;i<size;i++){ TreeNode* cur=que.front(); que.pop(); if(isSame(cur,t)) return true; if(cur->left) que.push(cur->left); if(cur->right) que.push(cur->right); } } return false; } bool isSame(TreeNode* s,TreeNode* t){ if(s==NULL&&t!=NULL) return false; else if(s!=NULL&&t==NULL) return false; else if(s==NULL&&t==NULL) return true; else if(s->val!=t->val) return false; bool leftside=isSame(s->left,t->left); bool rightsize=isSame(s->right,t->right); return leftside&&rightsize; } };

100. 相同的树

100. 相同的树 给定两个二叉树，编写一个函数来检验它们是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 示例 2: 输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false 示例 3: 输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false

和对称的数相似 只需要改变比较顺序

class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==NULL&&q!=NULL) return false; else if(p!=NULL&&q==NULL) return false; else if(p==NULL&&q==NULL) return true; else if(p->val!=q->val) return false; bool left=isSameTree(p->left,q->left); bool right=isSameTree(p->right,q->right); return left&&right; } };