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; } };