二叉树的题目，咕咕咕

1.小结论

性质：二叉树0度结点n0个，2度结点n2个，则n0=n2+1

(a个2度，b个1度，c个0度（叶节点），边数2a+b(所有的子节点数，度数代表子节点数),边数也是a+b+c-1(总结点数-1），所以a=c-1)

完全二叉树有2n个结点，叶子结点（n）个（n0+n1+n2=2n,n0=n2+1,2n0=2n-n1+1,在完全二叉树中n1只可能是0或1，都带入，结点没有小数，所以n0=n）

一棵完全二叉树结点531，高度（10）（最后一层至少1个结点，最多2^(h-1）个，那么得出结论

2^(h-1)<=总结点<=2^h-1)

二叉树中序遍历bacde,后序遍历bdeca,前序遍历（abcde）

(后序遍历得出根节点为a,由中序遍历得b为左子树，cde为右子树，由后序遍历得c为右子树的根结点为c，由中序遍历知道de都是c的右子树，由后序遍历知道d是e的根结点)

2.咕

144. 二叉树的前序遍历 - 力扣（LeetCode）

class Solution {private:vector<int> result;void preorder(TreeNode* root){if(root==NULL) return;result.push_back(root->val);preorder(root->left);preorder(root->right);}public:vector<int> preorderTraversal(TreeNode* root) {result.clear();//确保多次调用时准确preorder(root);return result;}

3.咕咕咕

145. 二叉树的后序遍历 - 力扣（LeetCode）

class Solution {private:vector<int> result;void postorder(TreeNode* root){if(root==NULL) return;postorder(root->left);postorder(root->right);result.push_back(root->val);}
public:vector<int> postorderTraversal(TreeNode* root) {result.clear();postorder(root);return result;}
};

4.咕咕咕咕

94. 二叉树的中序遍历 - 力扣（LeetCode）

class Solution {private:vector<int> result;void postorder(TreeNode* root){if(root==NULL) return;postorder(root->left);postorder(root->right);result.push_back(root->val);}
public:vector<int> postorderTraversal(TreeNode* root) {result.clear();postorder(root);return result;}
};

5.咕咕咕咕咕

965. 单值二叉树 - 力扣（LeetCode）

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

class Solution {private:unordered_set<int> result;//不在乎顺序，会自动去重void travese(TreeNode* root){if(root==NULL) return;result.insert(root->val);travese(root->left);travese(root->right);}
public:bool isUnivalTree(TreeNode* root) {result.clear();travese(root);return result.size()<=1;}
};

6.咕咕咕咕咕咕

100. 相同的树 - 力扣（LeetCode）

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

7.咕咕咕咕咕咕咕

101. 对称二叉树 - 力扣（LeetCode）

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

8.咕咕咕咕咕咕咕咕

572. 另一棵树的子树 - 力扣（LeetCode）

class Solution {private:// 判断两棵树是否完全相同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);}public: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);}
};

9.咕咕咕咕咕咕咕咕咕

二叉树遍历_牛客题霸_牛客网

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

#include <iostream>
#include <string>
using namespace std;struct TreeNode {char val;TreeNode* left;TreeNode* right;TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};// 递归构建二叉树
TreeNode* buildTree(string& s, int& index) {if (index >= s.length() || s[index] == '#') {index++;return nullptr;}TreeNode* node = new TreeNode(s[index++]);node->left = buildTree(s, index);node->right = buildTree(s, index);return node;
}// 中序遍历输出
void inorderTraversal(TreeNode* root) {if (root == nullptr) return;inorderTraversal(root->left);cout << root->val << " ";inorderTraversal(root->right);
}int main() {string s;while (cin >> s) {  // 处理多组输入int index = 0;TreeNode* root = buildTree(s, index);inorderTraversal(root);cout << endl;}return 0;
}