中国十大购物网站_网站整体设计意图及其功能_微商店铺怎么开通_市场营销方案怎么做

二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0)，n=0时为空树，n>0时为非空树。对于非空树:

有且仅有一个根结点；
除根结点外的其余结点又可分为两个不相交的子集，分别称为T 的左子树和右子树，且左子树和右子树本身又都是二叉树。

二叉树性质

任意二叉树第 i ii 层最大结点数为2^(i-1) (i>=1)
深度为 k kk 的二叉树最大结点总数为2^k − 1 。 ( k ≥ 1 )
对于任意二叉树，用n0,n1,n2分别表示叶子结点，度为1的结点，度为2的结点的个数，则有关系式n 0 = n 2 + 1
n个结点完全二叉树深度为⌊log2n⌋ + 1

二叉树分类

二叉树主要分为四类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树。

满二叉树

满二叉树就是除了叶子节点，其它节点都有左右子树，是一种特殊的完全二叉树：

满二叉树有个优势，就是它的节点个数很好算。假设深度为 h，那么总节点数就是 2^h - 1，等比数列求和。

完全二叉树

完全二叉树是指，除了最后一层，二叉树其他每层都必须是满的，且最下面一层的节点都集中在该层最左边的若干位置：

如下：

平衡二叉树

平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值小于2。如下图：

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树，也叫二叉排序树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉搜索树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树：

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是log(n)。

二叉树存储方式

顺序存储

使用一组地址连续的存储单元存储，例如数组。为了在存储结构中能得到父子结点之间的映射关系，二叉树中的结点必须按层次遍历的顺序存放。具体是：

对于完全二叉树，只需要自根结点起从上往下、从左往右依次存储。
对于非完全二叉树，首先将它变换为完全二叉树，空缺位置用某个特殊字符代替（比如#），然后仍按完全二叉树的存储方式存储。

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

链式存储

对每个结点，除数据域外再多增加左右两个指针域，分别指向该结点的左孩子和右孩子结点，再用一个头指针指向根结点。对应的存储结构：

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

递归解法：

/*** 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> ans;vector<int> inorderTraversal(TreeNode* root) {//1.递归---左根右if(!root) return {};inorderTraversal(root->left);ans.push_back(root->val);inorderTraversal(root->right);  return ans;}
}

迭代解法：

/*** 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> ans;vector<int> inorderTraversal(TreeNode* root) {//迭代---栈stack<TreeNode*> st;TreeNode* cur = root;while(cur || !st.empty()) {while(cur){st.push(cur);cur = cur->left;}cur = st.top();st.pop();ans.push_back(cur->val);cur = cur->right;}return ans;}
};

二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

/*** 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 maxDepth(TreeNode* root) {// if(!root) return 0;// int l = maxDepth(root->left);// int r = maxDepth(root->right);// return 1 + max(l,r);if(!root) return 0;TreeNode* cur = root;queue<TreeNode*> q;int ans = 0;q.push(root);while(!q.empty()){ans++;int n = q.size();for(int i = 0;i < n;i++){cur = q.front();q.pop();if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}}return ans;}
};

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

/*** 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) return nullptr;//先序// TreeNode* t = root->left;// root->left = root->right;// root->right = t;// invertTree(root->left);// invertTree(root->right);// return root;//后序TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;}
};

对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

/*** 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 isSymmetric(TreeNode* root) {if(!root) return true;return dfs(root->left,root->right);}bool dfs(TreeNode* l,TreeNode* r){if( !l && !r) return true;else if((l && !r) || (!l && r) || (l && r && l->val != r->val)) {return false;}else {return dfs(l->left,r->right) && dfs(l->right,r->left);}}
};

二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

/*** 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 ans = 0;int diameterOfBinaryTree(TreeNode* root) {if(!root) return 0;int l  = maxHeight(root->left);int r = maxHeight(root->right);ans = max(l+r,ans);diameterOfBinaryTree(root->left);diameterOfBinaryTree(root->right);return ans;}int maxHeight(TreeNode* root){if(!root) return 0;int l = maxHeight(root->left);int r = maxHeight(root->right);return 1 + max(l,r);}
};

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

/*** 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<vector<int>> levelOrder(TreeNode* root) {if(!root) return {};queue<TreeNode*> q;vector<vector<int>> ans;q.push(root);TreeNode* cur = root;while(!q.empty()){vector<int> temp;int n = q.size();for(int i = 0;i < n;i++){cur = q.front();q.pop();temp.push_back(cur->val);if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}ans.push_back(temp);}return ans;}
};

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵
平衡二叉搜索树。

/*** 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* sortedArrayToBST(vector<int>& nums) {return dfs(nums,0,nums.size()-1); }TreeNode* dfs(vector<int> &nums,int l,int r){if(l > r) return nullptr;int mid = (l + r)/2;TreeNode* root = new TreeNode();root->left = dfs(nums,l,mid-1);root->val = nums[mid];root->right = dfs(nums,mid+1,r);return root;}
};

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

/*** 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:long long pre = LLONG_MIN;bool isValidBST(TreeNode* root) {if(!root) return true;if(!isValidBST(root->left)) return false;if(pre >= root->val) return false;pre = root->val;return isValidBST(root->right);}
};

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 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:int count = 0,ans;int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ans;}void dfs(TreeNode* root){if(!root || !count) return;dfs(root->left);count--;if(count == 0){ans = root->val;}dfs(root->right);}
};

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

/*** 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:void flatten(TreeNode* root) {if(!root) return;TreeNode* cur = root;while(cur) {cout<<cur->val<<endl;if(cur->left){TreeNode* t = cur->left;while(t->right) t = t->right;t->right = cur->right;cur->right = cur->left;cur->left = nullptr;}cur = cur->right;}return;}
};

将前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

/*** 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:unordered_map<int,int> hash;TreeNode* build(vector<int>& pre,vector<int>& in,int pl,int pr,int il,int ir){if(pl > pr || ir < il){return nullptr;}TreeNode* root = new TreeNode(pre[pl]);int pos = hash[pre[pl]];root->left = build(pre,in,pl+1,pl+pos-il,il,pos-1);root->right = build(pre,in,pl+pos-il+1,pr,pos+1,ir);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();for(int i = 0;i < n;i++){hash[inorder[i]] = i;}return build(preorder,inorder,0,n-1,0,n-1);}
};

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root) return root;if(root == p || root == q) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(!left && right) return right;if(!right && left) return left;if(left && right) return root;return NULL;}
};

二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

/*** 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 ans = INT_MIN;int maxPathSum(TreeNode* root) {dfs(root);return ans;}int dfs(TreeNode* root){if(!root) return 0;int left = max(0,dfs(root->left));int right = max(0,dfs(root->right));ans = max(ans,root->val + left + right);return root->val + max(left,right);}
};

路径总和III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

/*** 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 RootSum(TreeNode* root,long long targetSum){if(!root) return 0;int ans = 0;if(root->val == targetSum) ans++;ans += RootSum(root->left,targetSum-root->val);ans += RootSum(root->right,targetSum-root->val);return ans;}int pathSum(TreeNode* root, int targetSum) {if(!root) return 0;int ans = RootSum(root,targetSum);ans += pathSum(root->left,targetSum);ans += pathSum(root->right,targetSum);return ans;}
};