LeetCode-樹-簡單-108-110-111
108、將有序數組轉化為二叉搜索樹
給你一個整數數組 nums ，其中元素已經按升序排列，請你將其轉換為一棵高度平衡二叉搜索樹。（高度平衡二叉樹是一棵滿足「每個節點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。）
個人分析：一個數組按照升序排列，其實就是一棵二叉搜索樹進行中序遍歷序列。僅知道中序遍歷序列不能唯一確定一棵二叉樹，加上高度平衡這個條件也不能唯一確定，所以一題多解。為了保證平衡，就要保證根一定是升序序列的中間位置的數進行遞歸排列。代碼如下：
class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sort(nums,0,nums.length-1); } public TreeNode sort(int[] nums,int low,int high) { //遞歸出口 if(low>high) { return null; } //防止溢出 int mid = low + (high-low)/2; TreeNode root = new TreeNode(nums[mid]); root.left = sort(nums,low,mid-1); root.right = sort(nums,mid+1,high); return root; }
其中尋找中間位置的數使用 int mid = low + (high-low)/2; 而不是用 int mid = (low +high)/2; 是為了防止int數值溢出。
110、判斷是否為平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。（本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過1。）
個人分析：獲得左子樹和右子樹的最大深度，然后比較深度差是否不超過1。
class Solution { public boolean isBalanced(TreeNode root) { //這個遞歸根據深度判斷是否平衡 if(root==null){ return true; } if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){ return false; } return isBalanced(root.left) && isBalanced(root.right); } public int maxDepth(TreeNode root){ //遞歸退出條件 if(root==null){ return 0; } return 1+Math.max(maxDepth(root.left),maxDepth(root.right)); } }
111、二叉樹的最小深度
給定一個二叉樹，找出其最小深度。最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
個人分析：求最小深度其實和求最大深度差不多，不過需要注意的是，null節點構不成子樹。
class Solution { public int minDepth(TreeNode root) { //樹本身為空 if(root == null){ return 0; } // //判斷左子樹為空右子樹不為空 // if(root.left==null && root.right!=null){ // return 1+minDepth(root.right); // } // //判斷右子樹為空左子樹不為空 // if(root.left!=null && root.right==null){ // return 1+minDepth(root.left); // } // return Math.min(minDepth(root.left),minDepth(root.right))+1; int lMinDepth = minDepth(root.left); int rMinDepth = minDepth(root.right); return root.left==null || root.right==null ? lMinDepth + rMinDepth + 1 : Math.min(lMinDepth,rMinDepth)+1; } }
浙公網安備 33010602011771號