代碼隨想錄：二叉樹
滿二叉樹：只有度為0和度為2的節(jié)點，且度為0的節(jié)點在同一層，這棵樹深度為k，有2^k-1個節(jié)點
完全二叉樹：底層可以不滿其他每層都填滿，并且底層的節(jié)點從左到右填充
二叉搜索樹：有數(shù)值，若左子樹不為空則左子樹上所有節(jié)點的值小于根節(jié)點的值，若右子樹不為空則右子樹上所有節(jié)點的值大于根節(jié)點的值，這棵樹的左右子樹也都是二叉搜索樹
平衡二叉搜索樹：空樹或左右兩個子樹高度差絕對值不超過1且都是平衡二叉搜索樹
C++中map,set的底層實現(xiàn)都是平衡二叉搜索樹所以map,set的增刪操作時間復(fù)雜度為Olog(n)
二叉樹的存儲方式可以鏈?zhǔn)酱鎯σ部梢皂樞虼鎯?，鏈?zhǔn)酱鎯Φ姆绞绞褂弥羔?，順序存儲使用?shù)組，數(shù)組存儲的二叉樹的遍歷方式是如果父節(jié)點數(shù)組下標(biāo)i則左孩子下標(biāo)2*i+1右孩子下標(biāo)2*i+2
用鏈?zhǔn)酱鎯Ρ硎镜亩鏄涓子诶斫馑砸话阌面準(zhǔn)酱鎯?/p>
二叉樹的兩種遍歷方式，深度優(yōu)先遍歷和廣度優(yōu)先遍歷
深度優(yōu)先遍歷包括前中后序遍歷，前中后指的是中間節(jié)點的遍歷順序，前序遍歷中->左->右，中序遍歷左->中->右，后序遍歷左->右->中
二叉樹相關(guān)題目經(jīng)常使用遞歸實現(xiàn)深度優(yōu)先遍歷，廣度優(yōu)先遍歷一般是用隊列實現(xiàn)
二叉樹的性質(zhì)：二叉樹的第i層至多有2^(i-1)個節(jié)點，若葉節(jié)點數(shù)量為n0，度為2的節(jié)點數(shù)為n2則n0=n2+1，具有n個節(jié)點的完全二叉樹深度為log2(n)+1
如果對具有n個節(jié)點的完全二叉樹節(jié)點按層編號對任意節(jié)點i有：如果i=1則節(jié)點i為二叉樹的根，如果i>1則節(jié)點i的雙親為i/2，如果2i>n則節(jié)點無左孩子，如果2i+1>n則節(jié)點無右孩子，否則其右孩子為節(jié)點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.確定函數(shù)的參數(shù)和返回值 2.確定終止條件 3.確定單層遞歸的邏輯）
確定函數(shù)的參數(shù)和返回值：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)
????????????{
//指針訪問節(jié)點一直到最底層
????????????????stack.Push(cur);
????????????????cur?=?cur.left;
//訪問的節(jié)點入棧
????????????}
????????????else
????????????{
//棧里彈出的就是要處理的節(jié)點
????????????????cur=stack.Pop();
????????????????result.Add(cur.val);
//處理的節(jié)點下面沒有子節(jié)點就把他彈出去，val加到結(jié)果中
????????????????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;
????}
}
//用遞歸的方法相對簡單且不容易出錯，耗時和內(nèi)存與非遞歸差距不大
前中后序遍歷可以用迭代法寫成統(tǒng)一的風(fēng)格，但較為不好理解，所以這種二叉樹問題建議使用遞歸法
層序遍歷，就是從左到右一層一層遍歷二叉樹，需要借助一個輔助數(shù)據(jù)結(jié)構(gòu)隊列實現(xiàn)
代碼如下
力扣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);
//根節(jié)點入隊
????????}
????????while?(queue.Count!=0)
????????{
//隊列里有元素說明還在這一層，將隊列中的元素彈出然后將彈出的元素的子節(jié)點加入隊列
????????????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：翻轉(zhuǎn)二叉樹
public?class?Solution?{
//只要遍歷二叉樹交換每個結(jié)點的左右兒子就餓能夠反轉(zhuǎn)整個二叉樹
????public?void?TreeSwap(TreeNode?root)
????{
????????TreeNode?temp?=?new?TreeNode();
????????temp?=?root.left;
????????root.left?=?root.right;
????????root.right?=?temp;
//定義交換左右兒子的操作
????}
????public?TreeNode?InvertTree(TreeNode?root)?{
//參數(shù)和返回值，返回的是一棵二叉樹，參數(shù)是根節(jié)點
????????if?(root==null)
????????{
????????????return?root;
//終止條件
????????}
????????TreeSwap(root);
????????InvertTree(root.left);
????????InvertTree(root.right);
//單層遞歸的邏輯，先反轉(zhuǎn)當(dāng)前節(jié)點的左右兒子，再分別反轉(zhuǎn)他的左右樹
????????return?root;
????}
}
//使用遞歸就先思考遞歸的三要素：參數(shù)和返回值，終止條件，單層遞歸的邏輯
力扣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);
//除了上面幾種情況就是左右節(jié)點值相同的情況，這時就比較左節(jié)點的左子樹和右節(jié)點的右子樹，左節(jié)點的右子樹和右節(jié)點的左子樹
????????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（加上當(dāng)前根節(jié)點的1）就是當(dāng)前根節(jié)點深度
????}
????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;
????????}
//終止條件，第一次做時出現(xiàn)了很嚴(yán)重的誤區(qū)，這里最小深度是指根節(jié)點到葉子節(jié)點的深度，只有左右兒子都為空的才是葉子節(jié)點，因此當(dāng)出現(xiàn)左兒子為空右兒子不為空或左兒子不為空右兒子為空的時候需要單獨計算該節(jié)點的最小深度
????????int?depth?=?Math.Min(GetDepth(root.left),?GetDepth(root.right))+1;
//左右子樹深度取最小加上根節(jié)點的1
????????return?depth;
????}
????public?int?MinDepth(TreeNode?root)?{
????????return?GetDepth(root);
????}
}
力扣110：平衡二叉樹
public?class?Solution?{
//還是用遞歸，求高度返回值是int，整道題返回值是bool，終止條件是遍歷到空節(jié)點返回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?+=?"->";
//左右兒子都為空說明是葉子節(jié)點，遇到葉子節(jié)點時就將之前所記錄的從根到葉子的path記錄到字符串中并在每兩個元素中間加上->，
????????????}
????????????spath?+=?Convert.ToString(path.Last());
//上面的循環(huán)不包括葉子節(jié)點，因為葉子節(jié)點后面不需要加->所以在這里單獨將葉子節(jié)點加到字符串中
????????????result.Add(spath);
????????????return;
????????}
????????if?(root.left!=null)
????????{
????????????Traversal(root.left,path,result);
????????????path.RemoveAt(path.Count-1);
//回溯和遞歸是一一對應(yīng)的，回溯就要和遞歸寫在一起而不是寫在外面，有遞歸就要有回溯
//第一次寫path.Remove(path.Last())在最后的測試中報錯了，這里用path.RemoveAt(path.Count-1)才能穩(wěn)定移除path中最后記錄的葉子節(jié)點
????????}
????????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：路經(jīng)總和
public?class?Solution?{
//初始化一個計數(shù)器為目標(biāo)和，每次遍歷減去遍歷到的節(jié)點的值，如果遍歷葉子節(jié)點時發(fā)現(xiàn)計數(shù)器內(nèi)值為0說明有符合條件的路徑
????bool?traversal(TreeNode?root,?int?count)
????{
????????if?(root.left==null&&?root.right==null&&?count==0)
????????{
????????????return?true;
//遇到葉子節(jié)點且計數(shù)為0直接返回true
????????}
????????if?(root.left==null&&?root.right==null)
????????{
????????????return?false;
//葉子節(jié)點但計數(shù)器不為0返回false
????????}
????????if?(root.left!=null)
????????{
????????????count?-=?root.left.val;
????????????if?(traversal(root.left,count))
????????????{
????????????????return?true;
????????????}
//左兒子處理
????????????count?+=?root.left.val;
//回溯，撤銷處理結(jié)果
????????}
????????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);
//進(jìn)行遍歷的節(jié)點計數(shù)器的值應(yīng)當(dāng)減去該節(jié)點內(nèi)的值
????}
}
力扣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里的結(jié)果，所以要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);
//先將根節(jié)點加入path中，否則返回的result里不會有根節(jié)點
????????traversal(root,targetSum-root.val);
????????return?result;
????}
}
力扣106：從中序遍歷與后序遍歷序列構(gòu)造二叉樹
public?class?Solution?{
//二叉樹后序遍歷數(shù)組最后一個元素一定是二叉樹的根，因此可以用這個元素將中序遍歷數(shù)組分成左右兩個數(shù)組，再利用中序遍歷和后序遍歷長度相同的特點將后序遍歷也分成左右兩個數(shù)組，再分別對每對左和右數(shù)組進(jìn)行分割，完成遞歸
????TreeNode?traversal(int[]?inorder,?int[]?postorder)
????{
????????if?(inorder.Length==0)
????????{
????????????return?null;
????????}
????????int?rootValue?=?postorder[postorder.Length?-?1];
????????TreeNode?root?=?new?TreeNode(){val?=?rootValue};
//找到根節(jié)點
????????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;
//根節(jié)點在中序遍歷數(shù)組對應(yīng)的下標(biāo)
????????????}
????????}
????????if?(rootIndex!=0)
????????{
????????????inorderLeft?=?inorder[0..rootIndex];
????????????postorderLeft?=?postorder[0..rootIndex];
//下標(biāo)不是0則說明有左側(cè)數(shù)組
????????}
????????if?(rootIndex!=inorder.Length-1)
????????{
????????????inorderRight?=?inorder[(rootIndex?+?1)..inorder.Length];
????????????postorderRight?=?postorder[rootIndex..(postorder.Length?-?1)];
//下標(biāo)不是最大值說明有右側(cè)數(shù)組，此時因為中序遍歷是從中間截斷，要去除中間的跟節(jié)點，而后續(xù)遍歷數(shù)組要去掉末尾的根節(jié)點因此中序遍歷右數(shù)組下標(biāo)(rootIndex?+?1)..inorder.Length后序遍歷數(shù)組下標(biāo)rootIndex..(postorder.Length?-?1)
????????}
????????root.left?=?traversal(inorderLeft,?postorderLeft);
????????root.right?=?traversal(inorderRight,?postorderRight);
//對左右數(shù)組分別遞歸得到左右子樹
????????return?root;
????}
????public?TreeNode?BuildTree(int[]?inorder,?int[]?postorder)
????{
????????TreeNode?result?=?new?TreeNode();
????????result?=?traversal(inorder,?postorder);
????????return?result;
????}
}
力扣105：從前序與中序遍歷序列構(gòu)造二叉樹
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);
????????
????}
}
前序與中序遍歷可以構(gòu)造出二叉樹，中序與后序遍歷可以構(gòu)造二叉樹，但是前序與后序遍歷不能構(gòu)造二叉樹，因為沒有中序遍歷無法判斷左右區(qū)間，無法確定二叉樹的分割點
力扣617：合并二叉樹
public?class?Solution?{
????public?TreeNode?MergeTrees(TreeNode?root1,?TreeNode?root2)?{
????????if?(root1==null)
????????{
????????????return?root2;
????????}
????????if?(root2==null)
????????{
????????????return?root1;
????????}
//當(dāng)一棵樹是空的時候合并完就是另一棵樹
????????root1.val?+=?root2.val;
//直接對root1進(jìn)行操作，將合并后的值儲存到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為空或找到符合條件的節(jié)點就把節(jié)點輸出
????????if?(root.val>val)
????????{
????????????return?SearchBST(root.left,?val);
//二叉搜索樹左節(jié)點一定比根小右節(jié)點一定比根大，所以當(dāng)前節(jié)點值比要找的數(shù)大就找他的左子樹，比要找的值小就找他的右子樹
????????}
????????if?(root.val<val)
????????{
????????????return?SearchBST(root.right,?val);
????????}
????????return?null;
//沒找到就返回空值
????}
}
力扣98：驗證二叉搜索樹
public?class?Solution
{
//二叉搜索樹中序遍歷得到的數(shù)組里面的元素一定是從小到大排列的，所以通過中序遍歷得到一個數(shù)組比較是否從小到大排列即可
????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
{
//和上一題類似，仍然是中序遍歷得到一個數(shù)組，這個數(shù)組是從小到大排列的，只要比較相鄰的每兩個數(shù)之間的差就能找到最小插值的絕對值
????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;
//節(jié)點的值范圍是0到10^5所以結(jié)果初始化為10^5+1
????????for?(int?i?=?1;?i?<?vec.Count;?i++)
????????{
????????????result?=?Math.Min(result,?vec[i]?-?vec[i?-?1]);
????????}
????????return?result;
????}
}
力扣501：二叉搜索樹中的眾數(shù)
public?class?Solution
{
//用一個Dictionary存儲每個節(jié)點的元素出現(xiàn)的次數(shù)
????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);
//出現(xiàn)了出現(xiàn)次數(shù)更多的元素就清空結(jié)果把新的加進(jìn)去，出現(xiàn)了出現(xiàn)次數(shù)一樣多的就直接把新的元素加進(jìn)去
????????????}
????????}
????????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;
//當(dāng)找到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;
//右子樹返回值不為空說明右子樹找到了要的值，將這個值作為結(jié)果返回
????????}
????????return?left;
//左子樹不為空就返回這個值
????}
}
力扣235：二叉搜索樹的最近公共祖先
public?class?Solution?{
//自根部向下搜索，若當(dāng)前節(jié)點的值比p和q都大說明p和q都在當(dāng)前節(jié)點的左子樹上，因此繼續(xù)搜索它的左子樹即可，反之搜索它的右子樹
????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：在二叉搜索樹中插入一個節(jié)點
public?class?Solution?{
????public?TreeNode?InsertIntoBST(TreeNode?root,?int?val)?{
????????if?(root==null)
????????{
????????????TreeNode?node?=?new?TreeNode(){val?=?val};
????????????return?node;
//通過遞歸函數(shù)的返回值對子節(jié)點進(jìn)行賦值
????????}
????????if?(root.val>val)
????????{
????????????root.left?=?InsertIntoBST(root.left,?val);
????????}
????????if?(root.val<val)
????????{
????????????root.right?=?InsertIntoBST(root.right,?val);
//遞歸將root.left和root.right指定為父節(jié)點
????????}
????????return?root;
????}
}
力扣450：刪除二叉搜索樹中的節(jié)點
public?class?Solution?{
????public?TreeNode?DeleteNode(TreeNode?root,?int?key)?{
????????if?(root==null)
????????{
????????????return?root;
//沒搜索到要刪除的數(shù)
????????}
????????if?(root.val==key)
????????{
????????????if?(root.left==null&&?root.right==null)
????????????{
????????????????return?root.left;
//要刪除的節(jié)點是葉子節(jié)點直接刪除
????????????}
????????????else?if?(root.left==null&&?root.right!=null)
????????????{
????????????????return?root.right;
//左兒子為空右兒子不為空直接刪除節(jié)點右兒子補(bǔ)上
????????????}
????????????else?if?(root.left!=null&&?root.right==null)
????????????{
????????????????return?root.left;
//右兒子為空左兒子不為空直接刪除節(jié)點右兒子補(bǔ)上
????????????}
????????????else
????????????{
????????????????TreeNode?cur?=?root.right;
????????????????while?(cur.left!=null)
????????????????{
????????????????????cur?=?cur.left;
????????????????}
????????????????cur.left?=?root.left;
????????????????root?=?root.right;
????????????????return?root;
//左右兒子都不為空將左兒子接到右兒子最左邊的節(jié)點的左邊然后返回右兒子
????????????}
????????}
????????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;
//當(dāng)前節(jié)點值小于左邊界的值則遞歸右子樹返回符合條件的頭節(jié)點
????????}
????????if?(root.val>high)
????????{
????????????TreeNode?left?=?TrimBST(root.left,?low,?high);
????????????return?left;
//當(dāng)前節(jié)點的值大于右邊界的值則遞歸左子樹返回符合條件的頭節(jié)點
????????}
????????root.left?=?TrimBST(root.left,?low,?high);
????????root.right?=?TrimBST(root.right,?low,?high);
//將返回的符合條件的左右頭節(jié)點分別賦值給root的左右孩子就完成了對二叉樹的剪枝
????????return?root;
????}
}
力扣108:將有序數(shù)組轉(zhuǎn)換為平衡二叉搜索樹
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時說明該區(qū)間內(nèi)是空節(jié)點
????????}
????????TreeNode?root?=?new?TreeNode()?{?val?=?nums[mid]?};
//作為根節(jié)點的中間元素就是數(shù)組最中間的數(shù)
????????root.left?=?SortedArrayToBST(nums[left..mid]);
//左閉右開區(qū)間，對左子樹和右子樹分別遞歸
????????root.right?=?SortedArrayToBST(nums[(mid?+?1)..(right+1)]);
????????return?root;
????}
}
總結(jié)：
二叉樹的構(gòu)造一般使用前序遍歷，先構(gòu)造中間節(jié)點，通過遞歸函數(shù)的返回值添加刪除節(jié)點
求普通二叉樹的屬性需要回溯就使用后序遍歷
求二叉搜索樹的屬性使用中序遍歷，二叉搜索樹中序遍歷后得到的是一個遞增的數(shù)組
