目录
965. 单值二叉树
100. 相同的树
101. 对称二叉树
144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历
572. 另一棵树的子树
TSINGK110 二叉树遍历
965. 单值二叉树
【题目链接】：https://leetcode.cn/problems/univalued-binary-tree/description/
先判断当前子树的左右节点是否和根相等，然后再去递归判断左右子树是否满足，不满足直接返回false
class Solution { public: bool isUnivalTree(TreeNode* root) { // 空树也是单值二叉树 if (root == nullptr) return true; // 检查左子节点 if (root->left != nullptr && root->left->val != root->val) return false; // 检查右子节点 if (root->right != nullptr && root->right->val != root->val) return false; // 递归验证左右子树 return isUnivalTree(root->left) && isUnivalTree(root->right); } };100. 相同的树
【题目链接】：https://leetcode.cn/problems/same-tree/
先判断跟是否相等，不相等就直接返回false，相等的话就去递归判断左右子树的根是否相等
class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { //同时为空 if(p == nullptr && q == nullptr) { return true; } //其中一个为空 if(p == nullptr || q == nullptr) { return false; } if(p->val != q->val) { return false; } return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); } };101. 对称二叉树
【题目链接】：https://leetcode.cn/problems/symmetric-tree/description/
判断一棵树是否对称，可以转化为判断它的左右子树是否互为镜像：
比较左子树的左节点与右子树的右节点
比较左子树的右节点与右子树的左节点
只要有一对对应节点不相等，就直接返回
false
class Solution { public: bool issame(TreeNode* p,TreeNode* q) { if(p==nullptr && q==nullptr) { return true; } if(p==nullptr || q==nullptr) { return false; } if(p->val != q->val) { return false; } return issame(p->left,q->right) && issame(p->right,q->left); } bool isSymmetric(TreeNode* root) { return issame(root->left,root->right); } };144. 二叉树的前序遍历
【题目链接】：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
这个递归版本很简单，上一章节我们就写到过，先访问根，然后访问左子树和右子树，如果遇到空直接返回
/*--------------------非递归版本---------------------*/ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; stack<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { // 访问左路节点 while (cur) { st.push(cur); v.push_back(cur->val); cur = cur->left; } // 访问左路节点的右子树 TreeNode* top = st.top(); st.pop(); cur = top->right; } return v; } };非递归版本理解起来有点难受，需要借助栈来完成
想要遍历这一颗树，可以先让左路节点入栈，然后通过访问栈顶节点的右路节点去访问整棵树，切记访问完后一定要出栈，避免影响下一个节点的访问
94. 二叉树的中序遍历
【题目链接】：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
中序遍历和前序遍历本质上两种写法都没区别，只不过访问根的时机变了
/*---------------------递归版本--------------------*/ class Solution { public: void _inorderTraversal(TreeNode* root,vector<int>& v) { if(root == nullptr) { return; } _inorderTraversal(root->left,v); v.push_back(root->val); _inorderTraversal(root->right,v); } vector<int> inorderTraversal(TreeNode* root) { vector<int> v; _inorderTraversal(root,v) ; return v; } };/*-----------------非递归版本--------------------*/ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while(cur || !st.empty()) { //入左路节点 while(cur) { st.push(cur); cur = cur->left; } //访问根节点 TreeNode* top = st.top(); st.pop(); v.push_back(top->val); //遍历当前节点的右子树 cur = top->right; } return v; } };145. 二叉树的后序遍历
【题目链接】：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
后序遍历的递归版本和前序、中序的递归只有访问根节点的时机有差别，别的一样；
但是非递归版本就有些不一样了，因为我们要判断何时将当前节点的左右子树都遍历了，也就是可以访问根了，有两种情况：
当前节点的右子树为空时，就可以访问根了，这是右子树为空的情况
定义一个节点prev，始终指向当前节点的上一个访问节点，只要prev == top->right，表示可以访问根节点了
/*----------------递归版本-----------------*/ class Solution { public: void _postorderTraversal(TreeNode* root,vector<int>& v) { if(root == nullptr) return; _postorderTraversal(root->left,v); _postorderTraversal(root->right,v); v.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> v; _postorderTraversal(root,v); return v; } };/*-----------------非递归版本-----------------*/ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* prev = nullptr; TreeNode* cur = root; while(cur || !st.empty()) { //入左路节点 while(cur) { st.push(cur); cur = cur->left; } //访问根节点 TreeNode* top = st.top(); if(top->right == nullptr || top->right == prev) { prev = top; st.pop(); v.push_back(top->val); } //访问左路节点的右子树 else { cur = top->right; } } return v; } };572. 另一棵树的子树
【题目链接】：https://leetcode.cn/problems/subtree-of-another-tree/description/
先判断root想subRoot是否相等，相等直接返回即可，不相等去判断左右子树是否和subRoot相等
class Solution { public: bool isSametree(TreeNode* p,TreeNode* q) { if(p == nullptr && q == nullptr) { return true; } if(p == nullptr || q == nullptr) { return false; } //根相等再去判断左右子树是否相等 return p->val == q->val && isSametree(p->left,q->left) && isSametree(p->right,q->right); } bool isSubtree(TreeNode* root, TreeNode* subRoot) { //根和子树先比较是否相等 //根的左 和 右 分别在比 //如果到叶子结点了依旧没找到相同的子树那就代表当不存在 if(root == nullptr) { return false; } if (isSametree(root, subRoot)) return true; return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); } };TSINGK110 二叉树遍历
这道题看起来挺复杂，其实只要思路清晰其实还是很简单的
1、读取字符串
2、以前序遍历构建树
3、中序遍历打印
#include <iostream> #include<string> using namespace std; struct TreeNode { TreeNode* left; TreeNode* right; char val; }; void order(TreeNode* root) { if(root == nullptr) { return; } order(root->left); cout<<root->val<<" "; order(root->right); } TreeNode* creattree(string a,int& i) { if(a[i] == '#') { i++; return nullptr; } TreeNode* root = new TreeNode; root->val = a[i]; i++; root->left = creattree(a,i); root->right = creattree(a,i); return root; } int main() { string a; cin >> a; int i = 0; TreeNode* root = creattree(a,i); order(root); return 0; }以上是一些二叉树相关基础OJ题，希望对大家有帮助！！！
