?226.翻轉二叉樹 （前序，后序）
題目鏈接 | 文檔講解 |視頻講解 :?鏈接
?1.思路：
-
? ?翻轉的是指針，不是數值
-
? 前序遍歷和后序遍歷都可以
-
? 中序不行，中序遍歷的順序是左中右,反轉左指針后,到根節點，在反轉右節點(此時的右節點就是原先的左節點)，真正的右節點沒有被處理
2.舉例：
| 步驟 | 當前節點 | 操作 |
|---|---|---|
| 1 | 4 | 進入函數，調用?invertTree(2) |
| 2 | 2 | 調用?invertTree(1) |
| 3 | 1 | 左右為空，直接交換（沒變化） |
| 4 | 2 | 回到?2，調用?invertTree(3) |
| 5 | 3 | 左右為空，交換（沒變化） |
| 6 | 2 | 交換自己的左右子節點（2 的左右變成 3 和 1） |
| 7 | 4 | 回到?4，調用?invertTree(5) |
| 8 | 5 | 左右為空，交換（沒變化） |
| 9 | 4 | 最后交換自己的左右子節點（4 的左右變成 5 和 2） |
?2.代碼：
public TreeNode invertTree(TreeNode root) {//遞歸終止條件if(root==null){return null;}//遞歸的邏輯//左invertTree(root.left);//右invertTree(root.right);//中 最后交換當前節點的左右子節點TreeNode temp=root.left;root.left=root.right;root.right=temp;return root;}101. 對稱二叉樹(后序)
題目鏈接 | 文檔講解 |視頻講解：鏈接
?
1.思路：
1.二叉樹是否是對稱二叉樹,要比較的是左右子樹是不是可以相互翻轉,比較的是2棵樹，所說遞歸遍歷要同時遍歷兩顆樹
2.判斷的情況分為下面幾種：
? ? ?如果左子樹為空,右子樹不為空? 返回false
? ? ?如果右子樹為空,左子樹不為空? 返回false
? ? ?如果左子樹為空,右子樹為空??? 返回true
? ? ?如果左子樹不為空,右子樹不為空,但是左右子樹值不相等,返回false
3.如何比較元素是否相等
? ? 左子樹的左節點和右子樹的右節點進行比較
? ? 左子樹的右節點和右子樹的左節點進行比較
4.因為要遍歷左右節點,遍歷順序是左右中,所以本題只能是后序遍歷
?2.代碼：
public boolean isSymmetric(TreeNode root){return isSame(root.left,root.right);}public boolean isSame(TreeNode left,TreeNode right){//左節點為空 右節點不為空if(left==null && right!=null){return false;}//左節點不為空 右節點為空if(left!=null &&right==null){return false;}//左右節點均為空if(left==null &&left==null){return true;}//左右節點不為空 但值不相等if(left.val != right.val ){return false;}//比較外側boolean leftResult = isSame(left.left, right.right);//比較內側boolean rightResult = isSame(left.right, right.left);//中return leftResult && rightResult;}
104.二叉樹的最大深度（前序,后序）
題目鏈接 | 文檔講解 |視頻講解：鏈接
二叉樹的深度：前序遍歷 根節點到該節點的最長簡單路徑邊的條數或者節點數（從上到下 eg:井高度） 從1開始
二叉樹的高度：后序遍歷 指從該節點到葉子節點的最長簡單路徑邊的條數或者節點數（從下到上? eg:樓高度）從1開始
?1.思路：
? ? ? ?二叉樹的最大深度=二叉樹的最大高度，所以可以采取后序遍歷
? ? ? 遞歸計算的是當前節點左子樹和右子樹的高度，所以需要將當前節點加上，最后的值+
?2.代碼：
public int maxDepth(TreeNode root){//遞歸終止條件if(root==null){return 0;}//遞歸邏輯//左子樹最大深度int leftHeight=maxDepth(root.left);//右子樹最大深度int rightHeight=maxDepth(root.right);//返回左右子樹最大深度+1（當前節點深度）return Math.max(leftHeight,rightHeight)+1;}111.二叉樹的最小深度 （前序，后序）
題目鏈接 | 文檔講解 |視頻講解：鏈接
?1.思路：
-
題目上求的是最小深度，指的是從根節點到最近葉子結點的距離
-
本題代碼使用的是后序遍歷（前序遍歷也可以），其實求的是根節點到葉子節點的最小距離，就是求高度的過程，不過這個最小距離 也同樣是最小深度
-
因為求的是最小，而且求的是根節點到葉子節點的最小深度，所以需要排除左子樹或葉子樹為空的情況
?2.代碼：
public int minDepth(TreeNode root){//遞歸終止條件if(root==null){return 0;}//遞歸邏輯 （后續遍歷）int leftHeight =minDepth(root.left);int rightHeight =minDepth(root.right);//遞歸邏輯//左子樹為空，右子樹不為空if(root.left==null && root.right!=null){return rightHeight+1;}//右子樹為空，左子樹不為空if(root.left!=null && root.right==null){return leftHeight+1;}//左右子樹都不為空int result=Math.min(leftHeight,rightHeight)+1;return result;}
