C++ 二叉树代码
二叉树代码，见下
#include <iostream>
using namespace std;
template<typename T>
struct TreeNode{
T val;
TreeNode *left;
TreeNode *right;
TreeNode():val(0), left(NULL), right(NULL)
TreeNode(T x):val(x), left(NULL), right(NULL){}
};
template<typename T>
class Tree(){
private:
TreeNode<T> *nodes;
TreeNode<T> *root;
size_t nodeSize;
TreeNode<T> *Create(T a[], int size, int nodeId, T nullNode);
void visit(TreeNode<T> *node);
void preOrder(TreeNode<T> *node);
void inOrder(TreeNode<T> *node);
void postOrder(TreeNode<T> *node);
void levelOrder(TreeNode<T> *node);
public:
Tree();
Tree(int maxNodes);
~Tree();
TreeNode<T>* GetTreeNode(int id);
void CreateTree(T a[], int size, T nullNode);
void preOrderTraversal();
void inOrderTraversal();
void postOrderTraversal();
};
template<typename T>
Tree<T>::Tree(){
nodeSize = 100001;
nodes = new TreeNode<T>[nodeSize]
}
template<typename T>
Tree<T>::Tree(int maxNodes){
nodeSize = maxNodes;
nodes = new TreeNode<T>[nodeSize];
}
template<typename T>
TreeNode<T>* Tree<T>::GetTreeNode(int id){
return &nodes[id];
}
template<typename T>
void Tree<T>::visit(TreeNode<T> *node){
cout << node->val;
}
template<typename T>
void Tree<T>::preOrder(TreeNode<T> *node){
if(node){
visit(node);
preOrder(node->left);
preOrder(node->right);
}
}
template<typename T>
void Tree<T>::inOrder(TreeNode<T> *node){
if(node){
inOrder(node->left);
visit(node);
inOrder(node->right);
}
}
template<typename T>
void Tree<T>::postOrder(TreeNode<T> *node){
if(node){
postOrder(node->left);
postOrder(node->right);
visit(node);
}
}
template<typename T>
void Tree<T>::CreatTree(T a[], int size, T nullnode){
root = Create(a, size, 1, nullnode);
}
template<typename T>
TreeNode<T>* Tree<T>::Create(T a[], int size, int nodeId, T nullnode){
if(nodeId >= size || a[nodeId] == nullnode){
return NULL;
}
TreeNode<T> *nowNode = GetTreeNode(nodeId);
nowNode->val = a[nodeId];
nowNode->left = Create(a, size, nodeId*2, nullnode);
nowNode->right = Create(a, size, nodeId*2+1, nullnode);
return nownode;
}
template<typename T>
void Tree<T>::preOrderTraversal(){
preOrder(root);
}
template<typename T>
void Tree<T>::inOrderTraversal(){
inOrder(root);
}
template<typename T>
void Tree<T>::postOrderTraversal(){
postOrder(root);
}
int main()
{
cout << "Hello World";
return 0;
}二叉树代码，对应力扣，完全二叉树的节点个数
/**
* 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:
int countNodes(TreeNode* root) {
if(root == NULL){
return 0;
}
int lc = countNodes(root->left);
int rc = countNodes(root->right);
return lc + rc + 1;
}
};代码练习，对应力扣单值二叉树，代码见下
/**
* 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 isUnivalTree(TreeNode* root) {
if(root == NULL){
return true;
}
if(root->left){
if(root->val != root->left->val){
return false;
}
if(!isUnivalTree(root->left)){
return false;
}
}
if(root->right){
if(root->val != root->right->val){
return false;
}
if(!isUnivalTree(root->right)){
return false;
}
}
return true;
}
};代码四，对应力扣 二叉树的前序遍历，代码见下
/**
* 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:
vector<int> ret;
void preorder(TreeNode *root){
if(root){
ret.push_back(root->val);
preorder(root->left);
preorder(root->right);
}
}
vector<int> preorderTraversal(TreeNode* root) {
ret.clear();
preorder(root);
return ret;
}
};代码五，对应力扣，二叉树的中序遍历，代码见下
/**
* 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:
vector<int> ret;
void inorder(TreeNode *root){
if(root){
inorder(root->left);
ret.push_back(root->val);
inorder(root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
ret.clear();
inorder(root);
return ret;
}
};代码六，对应力扣，二叉树的后续遍历
/**
* 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 {
vector<int> ret;
void postorder(TreeNode *root){
if(root){
postorder(root->left);
postorder(root->right);
ret.push_back(root->val);
}
}
public:
vector<int> postorderTraversal(TreeNode* root) {
ret.clear();
postorder(root);
return ret;
}
};代码，对应力扣，翻转二叉树，代码见下
/**
* 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:
TreeNode* invertTree(TreeNode* root) {
if(root == NULL){
return NULL;
}
TreeNode* l = invertTree(root->left);
TreeNode* r = invertTree(root->right);
root->left = r;
root->right = l;
return root;
}
};