算法笔记（六）—— 二叉树相关概念及经典算法题

二叉树的相关概念（判断方式）

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(root==nullptr||root==p||root==q)return root;TreeNode* left = lowestCommonAncestor(root->left , p , q);TreeNode* right = lowestCommonAncestor(root->right , p , q);if(left!=nullptr&&right!=nullptr){return root;}return left==nullptr?right:left;}
};

找一个节点中序遍历的后继节点（带父节点指针）

1. 节点有右树，则后继为右树上的最左节点

2. 节点无右树，往上走，看前节点是不是当前节点左孩子，如果是则当前节点为后继

二叉树序列化和反序列化

序列化：_表示值结束，#表示nullptr

反序列化：根据得到的字符串还原即可