军用棉被门网站建设,简单免费的制图软件,网站建设与管理小论文,河北制作网站模板建站公司二叉树的相关概念#xff08;判断方式#xff09;
1. 搜索二叉树#xff1a;对每棵子树#xff0c;左树比头小#xff0c;右树比头大。 中序遍历#xff0c;判断是否升序
2. 完全二叉树#xff1a;最后一层满或从左到右遍满。 宽度遍历#xff0c;如果有节点有右孩子…二叉树的相关概念判断方式
1. 搜索二叉树对每棵子树左树比头小右树比头大。 中序遍历判断是否升序
2. 完全二叉树最后一层满或从左到右遍满。 宽度遍历如果有节点有右孩子没左孩子返回false如果遇到第一个左右孩子不双全的情况那么接下来遇到的所有节点都必须是叶节点
3. 满二叉树节点个数 2^深度-1 左边子树需要满足满二叉树右边子树需要满足满二叉树
4. 平衡二叉树对任何一个子树左树和右树高度差不超过1 4.1. 左子树平衡右子树平衡 4.2. 左树高度差和右树高度差之差不超过1 找俩个节点的最低公共祖先
方法一哈希表存储节点对应的父结点然后用哈希set来进行去重找第一个祖先。
方法二算法优化
/*** 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(rootnullptr||rootp||rootq)return root;TreeNode* left lowestCommonAncestor(root-left , p , q);TreeNode* right lowestCommonAncestor(root-right , p , q);if(left!nullptrright!nullptr){return root;}return leftnullptr?right:left;}
};
找一个节点中序遍历的后继节点带父节点指针
1. 节点有右树则后继为右树上的最左节点
2. 节点无右树往上走看前节点是不是当前节点左孩子如果是则当前节点为后继 二叉树序列化和反序列化
序列化_表示值结束#表示nullptr
反序列化根据得到的字符串还原即可
