Leetcode 刷題記錄 11 —— 二叉樹第二彈

本系列為筆者的 Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據標簽命名，記錄筆者總結的做題思路，附部分代碼解釋和疑問解答，01~07為C++語言，08及以后為Java語言。

01 二叉樹的層序遍歷

在這里插入圖片描述

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {//廣度優先遍歷 queue//1.創建queue集合，添加首節點Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);//2.遍歷tree，取出結點，判斷結點情況List<List<Integer>> results = new ArrayList<>();if(root == null){return results;}while(!queue.isEmpty()){int size = queue.size();List<Integer> result = new ArrayList<>();for(int i=0; i<size; i++){TreeNode node = queue.poll();result.add(node.val);//3.添加左右孩子結點if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}results.add(result);}return results;}
}

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

在這里插入圖片描述

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode sortedArrayToBST(int[] nums) {}
}

給定二叉搜索樹的中序遍歷，是否可以唯一地確定二叉搜索樹？答案是否定的。

如果增加一個限制條件，即要求二叉搜索樹的高度平衡，是否可以唯一地確定二叉搜索樹？答案仍然是否定的。

直觀地看，我們可以選擇中間數字作為二叉搜索樹的根節點，這樣分給左右子樹的數字個數相同或只相差 1，可以使得樹保持平衡。

方法一：遞歸

BST 是 Binary Search Tree（二叉搜索樹）的縮寫。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {//1.構建遞歸函數，傳遞左右區間參數return helper(nums, 0, nums.length-1);}public TreeNode helper(int[] nums, int left, int right){if(left > right){ //特殊情況判斷return null;}//2.添加當前root結點int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);//3.遞歸添加左右孩子結點root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

03 驗證二叉搜索樹

在這里插入圖片描述

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isValidBST(TreeNode root) {}
}

這啟示我們設計一個遞歸函數 helper(root, lower, upper) 來遞歸判斷，函數表示考慮以 root 為根的子樹，判斷子樹中所有節點的值是否都在 (l,r) 的范圍內（注意是開區間）。如果 root 節點的值 val 不在 (l,r) 的范圍內說明不滿足條件直接返回，否則我們要繼續遞歸調用檢查它的左右子樹是否滿足，如果都滿足才說明這是一棵二叉搜索樹。

方法一：遞歸

class Solution {public boolean isValidBST(TreeNode root) {//1.構建遞歸函數，傳遞左右區間參數return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean helper(TreeNode root, long lower, long upper){if(root == null){ //特殊情況判斷return true;}//2.判斷當前root結點if(root.val <= lower || root.val >= upper){return false;}//3.遞歸判斷左右孩子結點return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);}
}

Long.MIN_VALUE和Long.MAX_VALUE是啥？

Long.MIN_VALUE 是 -2^63，即 -9,223,372,036,854,775,808。代表 long 類型變量可以存儲的最小值。
Long.MAX_VALUE 是 2^63 - 1，即 9,223,372,036,854,775,807。代表 long 類型變量可以存儲的最大值。

方法二：中序遍歷

class Solution {public boolean isValidBST(TreeNode root) {if(root == null){return true;}//queue: 創建 -> 當前 -> 孩子//stack: 創建 -> 左移 -> 右移//1.創建Deque<TreeNode> stack = new LinkedList<>();long inorder = Long.MIN_VALUE;while(!stack.isEmpty() || root != null){//2.左移while(root != null){stack.push(root);root = root.left;}root = stack.pop();if(root.val <= inorder){return false;}inorder = root.val;//3.右移root = root.right;}return true;}
}

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

在這里插入圖片描述

方法一：遞歸

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int flag1, flag2;public int kthSmallest(TreeNode root, int k) {flag1 = k;flag2 = 0;return inorder(root);}//1.創建public int inorder(TreeNode root){if(root == null){return -1;}//2.左右孩子結點int left = inorder(root.left);if(left != -1){return left;}flag2++;if(flag2 == flag1){return root.val;}//3.返回return inorder(root.right);}
}

方法二：棧

05 二叉樹的右視圖

在這里插入圖片描述

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> rightSideView(TreeNode root) {}
}

方法一：深度優先搜索（stack）

class Solution {public List<Integer> rightSideView(TreeNode root) {Map<Integer, Integer> map = new HashMap<>(); //深度，valint maxDepth = -1; //標記//1.創建并加入Deque<TreeNode> nodeStack = new LinkedList<>();Deque<Integer> depthStack = new LinkedList<>();nodeStack.push(root);depthStack.push(0);while(!nodeStack.isEmpty()){//2.彈出并判斷TreeNode node = nodeStack.pop();int depth = depthStack.pop();if(node != null){maxDepth = Math.max(maxDepth, depth); //標記更新//?if(!map.containsKey(depth)){map.put(depth, node.val);}//3.左右孩子結點nodeStack.push(node.left);nodeStack.push(node.right);depthStack.push(depth + 1);depthStack.push(depth + 1);}}//?List<Integer> result = new ArrayList<>();for(int i=0; i<=maxDepth; i++){result.add(map.get(i));}return result;}
}

① Deque是啥意思？

Deque 是 Double Ended Queue（雙端隊列）的縮寫，是一個接口，常用實現有LinkedList和ArrayDeque，既可以用作隊列（先進先出），也可以用作棧（后進先出）。

② 這個代碼是怎么保證每次棧彈出的都是沒加入map的最右端結點？

因為棧是后進先出，右孩子會先被彈出訪問。所以在訪問該層節點時，第一個被訪問到的節點是右孩子，也就是該層最右邊的節點。

③ 為什么maxDepth 賦值為0，會出現解答錯誤？

當樹為空時，沒有層被訪問，maxDepth 應該還是未初始化狀態。
如果用 int maxDepth = 0;，說明認為至少訪問了一層深度（深度0）。
代碼循環從 0 到 maxDepth，會執行一次。
但實際上沒有節點，也沒往map中放任何數據，所以map.get(0)會返回null，結果列表加了一個null。
導致與預期的空列表([])不符。

方法二：廣度優先搜索（queue）

class Solution {public List<Integer> rightSideView(TreeNode root) {Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();int max_depth = -1;Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();Queue<Integer> depthQueue = new LinkedList<Integer>();nodeQueue.add(root);depthQueue.add(0);while (!nodeQueue.isEmpty()) {TreeNode node = nodeQueue.remove();int depth = depthQueue.remove();if (node != null) {// 維護二叉樹的最大深度max_depth = Math.max(max_depth, depth);// 由于每一層最后一個訪問到的節點才是我們要的答案，因此不斷更新對應深度的信息即可rightmostValueAtDepth.put(depth, node.val);nodeQueue.add(node.left);nodeQueue.add(node.right);depthQueue.add(depth + 1);depthQueue.add(depth + 1);}}List<Integer> rightView = new ArrayList<Integer>();for (int depth = 0; depth <= max_depth; depth++) {rightView.add(rightmostValueAtDepth.get(depth));}return rightView;}
}

為什么最后訪問到的才是最右邊節點？

rightmostValueAtDepth.put(depth, node.val); 不斷地更新當前深度對應的節點值。
訪問順序是每層從左到右，意味著：
- 最開始訪問的節點會寫入該層的值。
- 后面訪問的節點會覆蓋之前的值。
- 因為是從左往右訪問，最后訪問的節點就是最右節點。
最終 “rightmostValueAtDepth” 保存的，正是每一層的最右邊節點值。