代码随想录：二叉树
满二叉树：只有度为0和度为2的节点，且度为0的节点在同一层，这棵树深度为k，有2^k-1个节点
完全二叉树：底层可以不满其他每层都填满，并且底层的节点从左到右填充
二叉搜索树：有数值，若左子树不为空则左子树上所有节点的值小于根节点的值，若右子树不为空则右子树上所有节点的值大于根节点的值，这棵树的左右子树也都是二叉搜索树
平衡二叉搜索树：空树或左右两个子树高度差绝对值不超过1且都是平衡二叉搜索树
C++中map,set的底层实现都是平衡二叉搜索树所以map,set的增删操作时间复杂度为Olog(n)
二叉树的存储方式可以链式存储也可以顺序存储，链式存储的方式使用指针，顺序存储使用数组，数组存储的二叉树的遍历方式是如果父节点数组下标i则左孩子下标2*i+1右孩子下标2*i+2
用链式存储表示的二叉树更易于理解所以一般用链式存储
二叉树的两种遍历方式，深度优先遍历和广度优先遍历
深度优先遍历包括前中后序遍历，前中后指的是中间节点的遍历顺序，前序遍历中->左->右，中序遍历左->中->右，后序遍历左->右->中
二叉树相关题目经常使用递归实现深度优先遍历，广度优先遍历一般是用队列实现
二叉树的性质：二叉树的第i层至多有2^(i-1)个节点，若叶节点数量为n0，度为2的节点数为n2则n0=n2+1，具有n个节点的完全二叉树深度为log2(n)+1
如果对具有n个节点的完全二叉树节点按层编号对任意节点i有：如果i=1则节点i为二叉树的根，如果i>1则节点i的双亲为i/2，如果2i>n则节点无左孩子，如果2i+1>n则节点无右孩子，否则其右孩子为节点2i+1
二叉树的定义：
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode()
{
this.val = val;
this.left = left;
this.right = right;
}
}
前中后序的递归遍历
（递归算法的三个要素：1.确定函数的参数和返回值 2.确定终止条件 3.确定单层递归的逻辑）
确定函数的参数和返回值：void traversal(TreeNode cur, LinkedList<int> vec)
确定终止条件：if (cur==null)return;
单层递归的逻辑：vec.AddLast(cur.val);//中
traversal(cur.left,vec);//左
traversal(cur.right,vec);//右
完整代码如下
力扣题号144：二叉树的前序遍历
public class Solution {
//递归法
void traversal(TreeNode cur, IList<int> vec)
{
if (cur==null)return;
vec.Add(cur.val);
traversal(cur.left,vec);
traversal(cur.right,vec);
}
public IList<int> PreorderTraversal(TreeNode root) {
IList<int> result=new List<int>();
traversal(root,result);
return result;
}
}
力扣94：二叉树的中序遍历
public class Solution {
//非递归，迭代法
public IList<int> InorderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
Stack<TreeNode> stack = new();
TreeNode cur = root;
while (cur!=null|| stack.Count!=0)
{
if (cur!=null)
{
//指针访问节点一直到最底层
stack.Push(cur);
cur = cur.left;
//访问的节点入栈
}
else
{
//栈里弹出的就是要处理的节点
cur=stack.Pop();
result.Add(cur.val);
//处理的节点下面没有子节点就把他弹出去，val加到结果中
cur = cur.right;
}
}
return result;
}
}
力扣145：二叉树的后序遍历
public class Solution {
void traversal(TreeNode cur, IList<int> vec)
{
if (cur==null)return;
traversal(cur.left,vec);
traversal(cur.right,vec);
vec.Add(cur.val);
}
public IList<int> PostorderTraversal(TreeNode root) {
IList<int> result=new List<int>();
traversal(root,result);
return result;
}
}
//用递归的方法相对简单且不容易出错，耗时和内存与非递归差距不大
前中后序遍历可以用迭代法写成统一的风格，但较为不好理解，所以这种二叉树问题建议使用递归法
层序遍历，就是从左到右一层一层遍历二叉树，需要借助一个辅助数据结构队列实现
代码如下
力扣102：二叉树的层序遍历
public class Solution
{
public IList<IList<int>> LevelOrder(TreeNode root)
{
IList<IList<int>> result = new List<IList<int>>();
Queue<TreeNode> queue = new Queue<TreeNode>();
if (root!=null)
{
queue.Enqueue(root);
//根节点入队
}
while (queue.Count!=0)
{
//队列里有元素说明还在这一层，将队列中的元素弹出然后将弹出的元素的子节点加入队列
int size = queue.Count;
IList<int> cur = new List<int>();
for (int i = 0; i < size; i++)
{
TreeNode node = queue.Dequeue();
cur.Add(node.val);
if (node.left!=null)
{
queue.Enqueue(node.left);
}
if (node.right!=null)
{
queue.Enqueue(node.right);
}
}
result.Add(cur);
}
return result;
}
}
力扣226：翻转二叉树
public class Solution {
//只要遍历二叉树交换每个结点的左右儿子就饿能够反转整个二叉树
public void TreeSwap(TreeNode root)
{
TreeNode temp = new TreeNode();
temp = root.left;
root.left = root.right;
root.right = temp;
//定义交换左右儿子的操作
}
public TreeNode InvertTree(TreeNode root) {
//参数和返回值，返回的是一棵二叉树，参数是根节点
if (root==null)
{
return root;
//终止条件
}
TreeSwap(root);
InvertTree(root.left);
InvertTree(root.right);
//单层递归的逻辑，先反转当前节点的左右儿子，再分别反转他的左右树
return root;
}
}
//使用递归就先思考递归的三要素：参数和返回值，终止条件，单层递归的逻辑
力扣101：对称二叉树
public class Solution {
public bool Compare(TreeNode left,TreeNode right)
{
//按题干要求返回布尔值
if (left==null&& right!=null)
{
return false;
}
else if (left!=null&& right==null)
{
return false;
}
else if (left==null&& right==null)
{
return true;
}
else if (left.val!=right.val)
{
return false;
}
//上面都是终止条件，分不同的情况讨论
bool outside=Compare(left.left,right.right);
bool inside=Compare(left.right, right.left);
//除了上面几种情况就是左右节点值相同的情况，这时就比较左节点的左子树和右节点的右子树，左节点的右子树和右节点的左子树
return outside && inside;
}
public bool IsSymmetric(TreeNode root) {
if (root==null)
{
return true;
}
return Compare(root.left, root.right);
}
}
力扣104：二叉树的最大深度
public class Solution {
public int GetDepth(TreeNode root)
{
//返回值要求是最大深度，类型为int
if (root==null)
{
return 0;
//终止条件为root为空
}
int depth = Math.Max(GetDepth(root.left), GetDepth(root.right))+1;
return depth;
//单层递归逻辑：求左右子树深度+1（加上当前根节点的1）就是当前根节点深度
}
public int MaxDepth(TreeNode root)
{
return GetDepth(root);
}
}
力扣111：二叉树的最小深度
public class Solution {
public int GetDepth(TreeNode root)
{
if (root==null)
{
return 0;
}
if (root.left==null&& root.right!=null)
{
return GetDepth(root.right) + 1;
}
if (root.right==null&& root.left!=null)
{
return GetDepth(root.left) + 1;
}
//终止条件，第一次做时出现了很严重的误区，这里最小深度是指根节点到叶子节点的深度，只有左右儿子都为空的才是叶子节点，因此当出现左儿子为空右儿子不为空或左儿子不为空右儿子为空的时候需要单独计算该节点的最小深度
int depth = Math.Min(GetDepth(root.left), GetDepth(root.right))+1;
//左右子树深度取最小加上根节点的1
return depth;
}
public int MinDepth(TreeNode root) {
return GetDepth(root);
}
}
力扣110：平衡二叉树
public class Solution {
//还是用递归，求高度返回值是int，整道题返回值是bool，终止条件是遍历到空节点返回0，单层逻辑是左右高度差绝对值大于一或左右子树求高度返回值是-1则说明不平衡返回-1
public int GetDepth(TreeNode root)
{
if (root==null)
{
return 0;
}
if (GetDepth(root.left)==-1)
{
return -1;
}
if (GetDepth(root.right)==-1)
{
return -1;
}
if (Math.Abs(GetDepth(root.left)-GetDepth(root.right))>1)
{
return -1;
}
else
{
return 1 + Math.Max(GetDepth(root.left), GetDepth(root.right));
}
}
public bool IsBalanced(TreeNode root)
{
return GetDepth(root) == -1 ? false : true;
}
}
力扣257：二叉树的所有路径
public class Solution {
void Traversal(TreeNode root, IList<int> path, IList<string> result)
{
//path的记录用栈的话每次都需要反向输出，所以使用IList记录
path.Add(root.val);
if (root.left==null&& root.right==null)
{
string spath="";
for (int i = 0; i < path.Count-1; i++)
{
spath += Convert.ToString(path[i]);
spath += "->";
//左右儿子都为空说明是叶子节点，遇到叶子节点时就将之前所记录的从根到叶子的path记录到字符串中并在每两个元素中间加上->，
}
spath += Convert.ToString(path.Last());
//上面的循环不包括叶子节点，因为叶子节点后面不需要加->所以在这里单独将叶子节点加到字符串中
result.Add(spath);
return;
}
if (root.left!=null)
{
Traversal(root.left,path,result);
path.RemoveAt(path.Count-1);
//回溯和递归是一一对应的，回溯就要和递归写在一起而不是写在外面，有递归就要有回溯
//第一次写path.Remove(path.Last())在最后的测试中报错了，这里用path.RemoveAt(path.Count-1)才能稳定移除path中最后记录的叶子节点
}
if (root.right!=null)
{
Traversal(root.right,path,result);
path.RemoveAt(path.Count-1);
}
}
public IList<string> BinaryTreePaths(TreeNode root)
{
IList<string> result = new List<string>();
IList<int> path = new List<int>();
if (root==null)
{
return result;
}
Traversal(root,path,result);
return result;
}
}
力扣112：路经总和
public class Solution {
//初始化一个计数器为目标和，每次遍历减去遍历到的节点的值，如果遍历叶子节点时发现计数器内值为0说明有符合条件的路径
bool traversal(TreeNode root, int count)
{
if (root.left==null&& root.right==null&& count==0)
{
return true;
//遇到叶子节点且计数为0直接返回true
}
if (root.left==null&& root.right==null)
{
return false;
//叶子节点但计数器不为0返回false
}
if (root.left!=null)
{
count -= root.left.val;
if (traversal(root.left,count))
{
return true;
}
//左儿子处理
count += root.left.val;
//回溯，撤销处理结果
}
if (root.right!=null)
{
count -= root.right.val;
if (traversal(root.right,count))
{
return true;
}
//右儿子
count += root.right.val;
}
return false;
}
public bool HasPathSum(TreeNode root, int targetSum) {
if (root==null)
{
return false;
}
return traversal(root, targetSum-root.val);
//进行遍历的节点计数器的值应当减去该节点内的值
}
}
力扣113：路径总和II
public class Solution
{
private IList<IList<int>> result = new List<IList<int>>();
private IList<int> path = new List<int>();
void traversal(TreeNode root, int count)
{
if (root.left==null&& root.right==null&& count==0)
{
result.Add(new List<int>(path));
//这里如果直接result.Add(path)后面会由于递归回溯改变path同时改变result里的结果，所以要new一个List放入result中
return;
}
if (root.left!=null)
{
path.Add(root.left.val);
count -= root.left.val;
traversal(root.left,count);
count += root.left.val;
path.RemoveAt(path.Count-1);
//递归回溯时不要忘记count和path都要回溯
}
if (root.right!=null)
{
path.Add(root.right.val);
count -= root.right.val;
traversal(root.right,count);
count += root.right.val;
path.RemoveAt(path.Count-1);
}
return;
}
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
result.Clear();
path.Clear();
if (root==null)
{
return result;
}
path.Add(root.val);
//先将根节点加入path中，否则返回的result里不会有根节点
traversal(root,targetSum-root.val);
return result;
}
}
力扣106：从中序遍历与后序遍历序列构造二叉树
public class Solution {
//二叉树后序遍历数组最后一个元素一定是二叉树的根，因此可以用这个元素将中序遍历数组分成左右两个数组，再利用中序遍历和后序遍历长度相同的特点将后序遍历也分成左右两个数组，再分别对每对左和右数组进行分割，完成递归
TreeNode traversal(int[] inorder, int[] postorder)
{
if (inorder.Length==0)
{
return null;
}
int rootValue = postorder[postorder.Length - 1];
TreeNode root = new TreeNode(){val = rootValue};
//找到根节点
int[] inorderLeft = new int[0], inorderRight = new int[0];
int[] postorderLeft = new int[0], postorderRight = new int[0];
int rootIndex = 0;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i]==rootValue)
{
rootIndex = i;
//根节点在中序遍历数组对应的下标
}
}
if (rootIndex!=0)
{
inorderLeft = inorder[0..rootIndex];
postorderLeft = postorder[0..rootIndex];
//下标不是0则说明有左侧数组
}
if (rootIndex!=inorder.Length-1)
{
inorderRight = inorder[(rootIndex + 1)..inorder.Length];
postorderRight = postorder[rootIndex..(postorder.Length - 1)];
//下标不是最大值说明有右侧数组，此时因为中序遍历是从中间截断，要去除中间的跟节点，而后续遍历数组要去掉末尾的根节点因此中序遍历右数组下标(rootIndex + 1)..inorder.Length后序遍历数组下标rootIndex..(postorder.Length - 1)
}
root.left = traversal(inorderLeft, postorderLeft);
root.right = traversal(inorderRight, postorderRight);
//对左右数组分别递归得到左右子树
return root;
}
public TreeNode BuildTree(int[] inorder, int[] postorder)
{
TreeNode result = new TreeNode();
result = traversal(inorder, postorder);
return result;
}
}
力扣105：从前序与中序遍历序列构造二叉树
public class Solution {
//思路与上一题完全相同，前序遍历序列的第一个元素就是二叉树的根
TreeNode traversal(int[] preorder, int[] inorder)
{
if (preorder.Length==0)
{
return null;
}
int rootValue = preorder[0];
TreeNode root = new TreeNode() { val = rootValue };
int rootIndex = 0;
for (int i = 0; i < inorder.Length; i++)
{
if (inorder[i]==rootValue)
{
rootIndex = i;
}
}
int[] preorderLeft = new int[0], inorderLeft = new int[0];
int[] preorderRight = new int[0], inorderRight = new int[0];
if (rootIndex!=0)
{
preorderLeft = preorder[1..(rootIndex+1)];
inorderLeft = inorder[0..(rootIndex)];
}
if (rootIndex!=inorder.Length-1)
{
preorderRight = preorder[(rootIndex + 1)..preorder.Length];
inorderRight = inorder[(rootIndex + 1)..inorder.Length];
}
root.left = traversal(preorderLeft, inorderLeft);
root.right = traversal(preorderRight, inorderRight);
return root;
}
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
return traversal(preorder, inorder);
}
}
前序与中序遍历可以构造出二叉树，中序与后序遍历可以构造二叉树，但是前序与后序遍历不能构造二叉树，因为没有中序遍历无法判断左右区间，无法确定二叉树的分割点
力扣617：合并二叉树
public class Solution {
public TreeNode MergeTrees(TreeNode root1, TreeNode root2) {
if (root1==null)
{
return root2;
}
if (root2==null)
{
return root1;
}
//当一棵树是空的时候合并完就是另一棵树
root1.val += root2.val;
//直接对root1进行操作，将合并后的值储存到root1里
root1.left = MergeTrees(root1.left, root2.left);
root1.right = MergeTrees(root1.right, root2.right);
return root1;
}
}
力扣700：二叉搜索树中的搜索
public class Solution {
public TreeNode SearchBST(TreeNode root, int val) {
if (root==null|| root.val==val)
{
return root;
}
//root为空或找到符合条件的节点就把节点输出
if (root.val>val)
{
return SearchBST(root.left, val);
//二叉搜索树左节点一定比根小右节点一定比根大，所以当前节点值比要找的数大就找他的左子树，比要找的值小就找他的右子树
}
if (root.val<val)
{
return SearchBST(root.right, val);
}
return null;
//没找到就返回空值
}
}
力扣98：验证二叉搜索树
public class Solution
{
//二叉搜索树中序遍历得到的数组里面的元素一定是从小到大排列的，所以通过中序遍历得到一个数组比较是否从小到大排列即可
private IList<int> vec = new List<int>();
void traversal(TreeNode cur)
{
if (cur==null)return;
traversal(cur.left);
vec.Add(cur.val);
traversal(cur.right);
}
public bool IsValidBST(TreeNode root) {
traversal(root);
for (int i = 1; i < vec.Count; i++)
{
if (vec[i]<=vec[i-1])
{
return false;
}
}
return true;
}
}
力扣530：二叉搜索树的最小绝对差
public class Solution
{
//和上一题类似，仍然是中序遍历得到一个数组，这个数组是从小到大排列的，只要比较相邻的每两个数之间的差就能找到最小插值的绝对值
private IList<int> vec = new List<int>();
void traversal(TreeNode cur)
{
if (cur==null)return;
traversal(cur.left);
vec.Add(cur.val);
traversal(cur.right);
}
public int GetMinimumDifference(TreeNode root) {
traversal(root);
if (vec.Count<2)
{
return 0;
}
int result = 100001;
//节点的值范围是0到10^5所以结果初始化为10^5+1
for (int i = 1; i < vec.Count; i++)
{
result = Math.Min(result, vec[i] - vec[i - 1]);
}
return result;
}
}
力扣501：二叉搜索树中的众数
public class Solution
{
//用一个Dictionary存储每个节点的元素出现的次数
private Dictionary<int, int> dic = new Dictionary<int, int>();
void traversal(TreeNode cur)
{
if (cur==null)return;
traversal(cur.left);
dic.TryAdd(cur.val,0);
//这里每次遇到新元素就要先为他添加一个key
dic[cur.val]++;
traversal(cur.right);
}
public int[] FindMode(TreeNode root)
{
IList<int> result = new List<int>();
if (root==null)
{
return result.ToArray();
}
traversal(root);
int count = 0;
foreach (var x in dic)
{
if (x.Value>count)
{
count = x.Value;
result.Clear();
result.Add(x.Key);
}
else if (x.Value==count)
{
result.Add(x.Key);
//出现了出现次数更多的元素就清空结果把新的加进去，出现了出现次数一样多的就直接把新的元素加进去
}
}
return result.ToArray();
}
}
力扣236：二叉树的最近公共祖先
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null)
{
return root;
//当找到p或q的时候就返回值
}
TreeNode left = LowestCommonAncestor(root.left, p, q);
TreeNode right = LowestCommonAncestor(root.right, p, q);
if (left!=null&& right!=null)
{
return root;
//回溯时将返回值一起返回
}
else if (left==null&& right!=null)
{
return right;
//右子树返回值不为空说明右子树找到了要的值，将这个值作为结果返回
}
return left;
//左子树不为空就返回这个值
}
}
力扣235：二叉搜索树的最近公共祖先
public class Solution {
//自根部向下搜索，若当前节点的值比p和q都大说明p和q都在当前节点的左子树上，因此继续搜索它的左子树即可，反之搜索它的右子树
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null)
{
return root;
}
if (root.val>p.val&& root.val>q.val)
{
TreeNode left = LowestCommonAncestor(root.left, p, q);
if (left!=null)
{
return left;
}
}
if (root.val<p.val&& root.val<q.val)
{
TreeNode right = LowestCommonAncestor(root.right, p, q);
if (right!=null)
{
return right;
}
}
return root;
}
}
力扣701：在二叉搜索树中插入一个节点
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root==null)
{
TreeNode node = new TreeNode(){val = val};
return node;
//通过递归函数的返回值对子节点进行赋值
}
if (root.val>val)
{
root.left = InsertIntoBST(root.left, val);
}
if (root.val<val)
{
root.right = InsertIntoBST(root.right, val);
//递归将root.left和root.right指定为父节点
}
return root;
}
}
力扣450：删除二叉搜索树中的节点
public class Solution {
public TreeNode DeleteNode(TreeNode root, int key) {
if (root==null)
{
return root;
//没搜索到要删除的数
}
if (root.val==key)
{
if (root.left==null&& root.right==null)
{
return root.left;
//要删除的节点是叶子节点直接删除
}
else if (root.left==null&& root.right!=null)
{
return root.right;
//左儿子为空右儿子不为空直接删除节点右儿子补上
}
else if (root.left!=null&& root.right==null)
{
return root.left;
//右儿子为空左儿子不为空直接删除节点右儿子补上
}
else
{
TreeNode cur = root.right;
while (cur.left!=null)
{
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
//左右儿子都不为空将左儿子接到右儿子最左边的节点的左边然后返回右儿子
}
}
if (root.val>key)
{
root.left = DeleteNode(root.left, key);
}
if (root.val<key)
{
root.right = DeleteNode(root.right, key);
}
return root;
}
}
力扣669：修剪二叉搜索树
public class Solution {
public TreeNode TrimBST(TreeNode root, int low, int high) {
if (root==null)
{
return root;
}
if (root.val<low)
{
TreeNode right = TrimBST(root.right, low, high);
return right;
//当前节点值小于左边界的值则递归右子树返回符合条件的头节点
}
if (root.val>high)
{
TreeNode left = TrimBST(root.left, low, high);
return left;
//当前节点的值大于右边界的值则递归左子树返回符合条件的头节点
}
root.left = TrimBST(root.left, low, high);
root.right = TrimBST(root.right, low, high);
//将返回的符合条件的左右头节点分别赋值给root的左右孩子就完成了对二叉树的剪枝
return root;
}
}
力扣108:将有序数组转换为平衡二叉搜索树
public class Solution {
public TreeNode SortedArrayToBST(int[] nums)
{
int left = 0, right = nums.Length - 1;
int mid = left + (right - left) / 2;
if (left>right)
{
return null;
//left大于right时说明该区间内是空节点
}
TreeNode root = new TreeNode() { val = nums[mid] };
//作为根节点的中间元素就是数组最中间的数
root.left = SortedArrayToBST(nums[left..mid]);
//左闭右开区间，对左子树和右子树分别递归
root.right = SortedArrayToBST(nums[(mid + 1)..(right+1)]);
return root;
}
}
总结：
二叉树的构造一般使用前序遍历，先构造中间节点，通过递归函数的返回值添加删除节点
求普通二叉树的属性需要回溯就使用后序遍历
求二叉搜索树的属性使用中序遍历，二叉搜索树中序遍历后得到的是一个递增的数组
