Leetcode：二叉樹

94. 二叉樹的中序遍歷

class Solution {public List<Integer> inorderTraversal(TreeNode root) {TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();List<Integer> list = new ArrayList<>();while (!stack.isEmpty() || cur != null) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();list.add(cur.val);cur = cur.right;}return list;}
}

230. 二叉搜索樹中第 K 小的元素

class Solution {public int kthSmallest(TreeNode root, int k) {Stack<TreeNode> stack = new Stack<>();int ans=0;TreeNode cur = root;while(!stack.isEmpty() || cur!=null){while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.pop();k--;if(k==0){ans=cur.val;return ans;}//必要的一步cur=cur.right;}return -1;}
}

104. 二叉樹的最大深度


class Solution {public int maxDepth(TreeNode root) {if(root==null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;}
}

226. 翻轉二叉樹

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null) return null;TreeNode temp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.right);return root;}
}

101. 對稱二叉樹


class Solution {public boolean isSymmetric(TreeNode root) {if(root==null) return true;return dfs(root.left, root.right);}public boolean dfs(TreeNode left, TreeNode right){if(left==null && right==null) return true;//兩個都nullif(left==null || right==null) return false;//一個null，另一個非空if(left.val!=right.val) return false;//兩個都非空return dfs(left.left, right.right) && dfs(right.left, left.right);}
}

543. 二叉樹的直徑

class Solution {private int maxDepth=0;public int diameterOfBinaryTree(TreeNode root) {if(root==null) return 0;depth(root);return maxDepth;}public int depth(TreeNode root){if(root==null) return 0;int lH = depth(root.left);int rH = depth(root.right);//注意：這里的lH+rH正好是路徑長度，應該是lH+rH+1-1，加和減的1都是重復的根節點maxDepth=Math.max(maxDepth, lH+rH);return Math.max(lH, rH)+1;}
}

102. 二叉樹的層序遍歷

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> ans = new ArrayList<>();if(root!=null){queue.add(root);}while(!queue.isEmpty()){int n = queue.size();List<Integer> arr = new ArrayList<>();for(int i=0; i<n; i++){TreeNode cur = queue.poll();arr.add(cur.val);if(cur.left!=null)queue.add(cur.left);if(cur.right!=null)queue.add(cur.right);}ans.add(arr);}return ans;}
}

199. 二叉樹的右視圖

class Solution {public List<Integer> rightSideView(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();List<Integer> ans = new ArrayList<>();if (root != null)queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();for (int i = 0; i < n ; i++) {TreeNode cur = queue.poll();if (cur.left != null)queue.offer(cur.left);if (cur.right != null)queue.offer(cur.right);if(i==n-1)ans.add(cur.val);}}return ans;}
}

108. 將有序數組轉換為二叉搜索樹

構造平衡二叉搜索樹！| LeetCode：108.將有序數組轉換為二叉搜索樹_嗶哩嗶哩_bilibili

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums, 0, nums.length-1);}public TreeNode build(int[] nums, int left, int right){//終止條件： middle-1到最后會比left小， middle+1會比right大if(left>right) return null;int middle = (left+right)/2;TreeNode root = new TreeNode(nums[middle]);root.left = build(nums, left, middle-1);root.right = build(nums, middle+1, right);return root;}
}

110. 平衡二叉樹

后序遍歷求高度，高度判斷是否平衡 | LeetCode：110.平衡二叉樹_嗶哩嗶哩_bilibili

class Solution {public boolean isBalanced(TreeNode root) {int res = dfs(root);return (res==-1) ? false : true;}//后續遍歷順序public int dfs(TreeNode root){if(root==null) return 0;int left = dfs(root.left);if(left==-1) return -1;int right = dfs(root.right);if(right==-1) return -1;if(Math.abs(left-right)>1)return -1;else{return Math.max(left, right) + 1;}}
}

98. 驗證二叉搜索樹(mid)

你對二叉搜索樹了解的還不夠！ | LeetCode：98.驗證二叉搜索樹_嗶哩嗶哩_bilibili

class Solution {long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root==null) return true;//左boolean left = isValidBST(root.left);//中if(root.val>pre)pre = root.val;elsereturn false;//右boolean right = isValidBST(root.right);return left && right;}
}

114. 二叉樹展開為鏈表

class Solution {public void flatten(TreeNode root) {TreeNode cur = root;if (root == null)return;while (cur != null) {if (cur.left != null) {TreeNode p = cur.left;//移動到cur節點的left的最右側節點while (p.right != null)p = p.right;//做連接p.right = cur.right;cur.right = cur.left;cur.left = null;}//做cur左邊的斷開cur = cur.right;}}
}

105. 從前序與中序遍歷序列構造二叉樹

坑很多！來看看你掉過幾次坑 | LeetCode：106.從中序與后序遍歷序列構造二叉樹_嗶哩嗶哩_bilibili

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int len = preorder.length;if(len==0) return null;int rootValue=preorder[0];TreeNode root = new TreeNode(rootValue);//獲取根節點indexint rootIndex = 0;for(int i=0; i<len; i++){if(inorder[i]==rootValue){rootIndex=i;break;}}int left_len = rootIndex;int right_len = len-rootIndex-1;;int[] preorder_left = Arrays.copyOfRange(preorder, 1, rootIndex+1);int[] preorder_right = Arrays.copyOfRange(preorder, rootIndex+1, len);int[] inorder_left = Arrays.copyOfRange(inorder, 0, rootIndex);        int[] inorder_right = Arrays.copyOfRange(inorder, rootIndex+1, len);//遞歸左右子樹root.left = buildTree(preorder_left, inorder_left);root.right = buildTree(preorder_right, inorder_right);return root;}
}

106. 從中序與后序遍歷序列構造二叉樹

坑很多！來看看你掉過幾次坑 | LeetCode：106.從中序與后序遍歷序列構造二叉樹_嗶哩嗶哩_bilibili


class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {int len = postorder.length;if(len==0) return null;int rootValue=postorder[len-1];TreeNode root = new TreeNode(rootValue);//獲取根節點indexint rootIndex = 0;for(int i=0; i<len; i++){if(inorder[i]==rootValue){rootIndex=i;break;}}int left_len = rootIndex;int right_len = len-rootIndex-1;;//前序+中序 或者 后序+中序 僅僅是切分數組有區別int[] postorder_left = Arrays.copyOfRange(postorder, 0, left_len);int[] postorder_right = Arrays.copyOfRange(postorder, rootIndex, left_len+right_len);int[] inorder_left = Arrays.copyOfRange(inorder, 0, rootIndex);        int[] inorder_right = Arrays.copyOfRange(inorder, rootIndex+1, len);//遞歸左右子樹root.left = buildTree(inorder_left, postorder_left);root.right = buildTree(inorder_right, postorder_right);return root;}
}

437. 路徑總和 III（?）

不用前綴和：

小姐姐刷題-Leetcode 437 路徑總和 III_嗶哩嗶哩_bilibili

class Solution {private int res = 0;public void dfs(TreeNode root, long sum) {if (root == null)return;if (root.val == sum) {res++;}dfs(root.left, sum-root.val);dfs(root.right, sum-root.val);}//這里的int需要改成longpublic int pathSum(TreeNode root, long targetSum) {if (root != null) {dfs(root, targetSum);// 這里targetSum不需要減當前節點的值，因為路徑不一定從根節點開始pathSum(root.left, targetSum);pathSum(root.right, targetSum);}return res;}
}

常規：前綴和+hashmap

力扣 leetcode 437. 路徑總和 III/dfs+前綴和+hashmap/建議倍速觀看/技術崗秋招之路，自我反思/刷題_嗶哩嗶哩_bilibili

class Solution {int res=0;long targetSum;Map<Long, Integer> map;public int pathSum(TreeNode root, long targetSum) {this.targetSum = targetSum;map=new HashMap<>();map.put(0L, 1); //long類型dfs(root, 0);return res;}public void dfs(TreeNode root, long sum){if(root==null) return;sum += root.val;if(map.containsKey(sum-targetSum)){res+=map.get(sum-targetSum);}map.put(sum, map.getOrDefault(sum, 0)+1 );dfs(root.left, sum);dfs(root.right, sum);//回溯map.put(sum, map.get(sum)-1);}}

236. 二叉樹的最近公共祖先

【自底向上查找，有點難度！ | LeetCode：236. 二叉樹的最近公共祖先】自底向上查找，有點難度！ | LeetCode：236. 二叉樹的最近公共祖先_嗶哩嗶哩_bilibili


class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return root;if(root==p || root==q) return root;//采用后續遍歷：//先處理左右TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);/然后處理中節點，要基于上面“左右”的結果來判斷“中”，所以是后續遍歷if(left==null && right!=null) return right;if(left!=null && right==null) return left; if(left==null && left==null) return null;return root;}
}