程式碼隨想錄 | 二叉樹
226. 翻轉二叉樹
給你一棵二叉樹的根節點 root ，翻轉這棵二叉樹，並返回其根節點。
輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]
ψ(｀∇´)ψ 我的思路
- 還是用了層序遍歷的方法，在該結點左右孩子入棧之後，互換左右指針
/**
* 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 invertTree(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (!que.isEmpty()) {
int size = que.size();
while (size > 0) {
TreeNode node = que.poll();
TreeNode tmp = new TreeNode();
if (node.right != null && node.left != null) {
//左右孩子都不空，右孩子、左孩子加入隊列並交換
que.add(node.right);
que.add(node.left);
tmp = node.right;
node.right = node.left;
node.left = tmp;
} else if (node.right==null&&node.left!=null ) {
que.add(node.left);
node.right=node.left;
node.left=null;
} else if(node.left==null&&node.right!=null){
que.add(node.right);
node.left=node.right;
node.right=null;
}
size--;
}
}
return root;
}
}
- 下面是遞歸的做法：
/**
* 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 invertTree(TreeNode root) {
if (root == null) {
return null;
}
//先序遍歷
swapChildren(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
101. 對稱二叉樹
給你一個二叉樹的根節點 root ， 檢查它是否軸對稱。
輸入：root = [1,2,2,3,4,4,3]
輸出：true
ψ(｀∇´)ψ 我的思路
- 層序遍歷每一層二叉樹，每一層結點的值放入鏈表，判斷鏈表（除第一層外）是否對稱
/**
* 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 isSymmetric(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (!que.isEmpty()){
int size = que.size();
List<Integer> list = new ArrayList<>();
while (size>0){
TreeNode node = que.poll();
list.add(node.val);//加入鏈表
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
//判斷list是不是對稱列表
if(list.size()>1){
Collections.reverse(list.subList(0,list.size()/2));
if(!list.subList(0,list.size()/2).equals(list.subList(list.size()/2,list.size()))){
return false;
}
}
}
return true;
}
}
-
上面的程式碼並不能判斷下面這種情況：
輸入：root = [1,2,2,null,3,null,3]
輸出：false -
因為只把不空的結點加入到鏈表，所以上述情況的鏈表是這樣的：[1][2,2][3,3],我想著把null也加入到鏈表裡。不行(x_x)，那樣的話就沒辦法控制臨界條件了。
-
下面是程式碼隨想錄的遞歸做法：比較根結點的左右子樹是否對稱
/**
* 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 isSymmetric(TreeNode root) {
boolean res = comparable(root.left, root.right);
return res;
}
public static boolean comparable(TreeNode left, TreeNode right){
if(left==null&&right!=null){return false;}
else if(right==null&&left!=null){return false;}
else if(right==null&&left==null){return true;}
else if(right.val!= left.val){return false;}
boolean a = comparable(left.left, right.right);//比較外側結點
boolean b = comparable(left.right, right.left);//比較內測結點
boolean res = a && b;
return res;
}
}
- 感覺遞歸的做法要好理解很多，再寫兩道類似的題目練一下遞歸
100. 相同的樹
給你兩棵二叉樹的根節點 p 和 q ，編寫一個函數來檢驗這兩棵樹是否相同。
如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。
/**
* 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 isSameTree(TreeNode p, TreeNode q) {
//if(p==null&&q==null){return false;}
return comparable(p,q);
}
public boolean comparable(TreeNode p,TreeNode q){
if(p!=null&&q==null){return false;}
else if(p==null&&q==null){return true;}
else if(p==null&&q!=null){return false;}
else if(p.val!=q.val){return false;}
boolean a = comparable(p.left,q.left);
boolean b = comparable(p.right,q.right);
return a && b;
}
}
572. 另一棵樹的子樹
給你兩棵二叉樹 root 和 subRoot 。檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。如果存在，返回 true ；否則，返回 false 。
二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有後代節點。tree 也可以看做它自身的一棵子樹。
/**
* 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 isSubtree(TreeNode root, TreeNode subRoot) {
//前序遍歷root
List<TreeNode> nodes = new ArrayList<>();
preorder(root,nodes);
for (TreeNode node : nodes) {
//此時nodes裡面是root中的所有結點
if(comparable(node, subRoot)){
return true;
}
}
return false;
}
public void preorder(TreeNode root, List<TreeNode> nodes){
if(root==null){return ;}
nodes.add(root);
preorder(root.left,nodes);
preorder(root.right,nodes);
}
public boolean comparable(TreeNode left,TreeNode right){
if(left==null&&right==null){return true;}
else if(left!=null&&right==null){return false;}
else if(left==null&&right!=null){return false;}
else if(left.val!= right.val){return false;}
boolean a = comparable(left.left, right.left);
boolean b = comparable(left.right, right.right);
return a && b;
}
}
104. 二叉樹的最大深度
- 這題昨天用層序遍歷寫過，下面是遞歸的實現：
/**
* 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 int maxDepth(TreeNode root) {
//這裡用根結點的高度表示二叉樹的最大深度
if(root==null){return 0;}
int leftDepth = maxDepth(root.left);//左孩子的高度
int rightDepth = maxDepth(root.right);//右孩子的高度
return Math.max(leftDepth,rightDepth)+1;//當前結點的高度（左孩子的高度，右孩子的高度的最大值+1）
//後序遍歷
}
}
- 感覺遞歸還是不太好理解
559. N 叉樹的最大深度
給定一個 N 叉樹，找到其最大深度。
最大深度是指從根節點到最遠葉子節點的最長路徑上的節點總數。
N 叉樹輸入按層序遍歷序列化表示，每組子節點由空值分隔
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root==null){return 0;}
List<Node> children = root.children;//當前結點的孩子們
int max = 0;
for (Node child : children) {
int depth = maxDepth(child);
max = Math.max(depth,max);
}
return max+1;
}
}
- 擴展成n叉樹，和二叉樹區別不大，就是孩子數不確定，用for循環遍歷求孩子的高度就好
111. 二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
說明：葉子節點是指沒有子節點的節點。
ψ(｀∇´)ψ 我的思路
- 稍微改了二叉樹最大深度的程式碼，
/**
* 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 int minDepth(TreeNode root) {
if(root==null){return 0;}//空的結點是第0層(也是遞歸出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
return Math.min(leftDepth,rightDepth)+1;
}
}
- 程式碼在運行下圖例子時返回1
題目中說的是：最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
- 在上述程式碼中，只有一個孩子的結點會被誤以為是葉子結點，返回該結點的高度。改進後程式碼如下：
/**
* 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 int minDepth(TreeNode root) {
if(root==null){return 0;}//空的結點是第0層(也是遞歸出口)
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left==null){return rightDepth+1;}//如果左子樹為空，返回右子樹的高度+1
else if(root.right==null){return leftDepth+1;}//如果右子樹為空，返回左子樹的高度+1
return Math.min(leftDepth,rightDepth)+1;
}
}
222. 完全二叉樹的節點個數
完全二叉樹 的根節點 root ，求出該樹的節點個數。
完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，並且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。
ψ(｀∇´)ψ 我的思路
- 層序遍歷，每彈出一個數count++
/**
* 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 int countNodes(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
if(root==null){return 0;}
int count = 0;
que.add(root);
while (!que.isEmpty()){
int size = que.size();
while (size>0){
count++;
TreeNode node = que.poll();
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
}
return count;
}
}
- 不知道是不是昨天層序遍歷做多了，我現在拿到題想的都是層序遍歷，遞歸好難想啊🤯
class Solution {
// 還是展示遞歸解法（後序遍歷）
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
- 離譜離譜，就這麼幾行
110. 平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。
ψ(｀∇´)ψ 我的思路
- 求出根結點左右子樹的最大高度，相減取絕對值不超過1即為平衡二叉樹
/**
* 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 isBalanced(TreeNode root) {
if(root==null){return true;}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
if(Math.abs(leftHeight-rightHeight)<=1){
return true;
} else{return false;}
}
public int maxHeight(TreeNode root){
if(root==null){return 0;}
return Math.max(maxHeight(root.left),maxHeight(root.right))+1;
}
}
- 按我的思路，這就是個平衡二叉樹，仔細讀題後發現：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。
- 應該在外面再套一個循環，但是那樣程式碼就太複雜了。下面是程式碼隨想錄的解法：
- 先來區分一下高度和深度（高度用後序遍歷，深度用前序遍歷）
上面的題目中有求二叉樹最大深度的題目，用到後序遍歷，是因為求二叉樹的最大深度就是求根結點的高度
/**
* 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 isBalanced(TreeNode root) {
//後序遍歷
int height = getHeight(root);
if(height==-1){return false;}
else return true;
}
public int getHeight(TreeNode root){
if(root==null){
return 0;//null結點高度為0
}
int leftHeight = getHeight(root.left);//左子樹的高度
if(leftHeight==-1){return -1;}
int rightHeight = getHeight(root.right);//右子樹的高度
if(rightHeight==-1){return -1;}
if(Math.abs(leftHeight-rightHeight)>1){return -1;}//當前結點左右子樹高度差>1
return 1+Math.max(leftHeight,rightHeight);//返回當前結點的高度
}
}
- 遞歸，遞歸，又是你！！！
257. 二叉樹的所有路徑
給你一個二叉樹的根節點 root ，按 任意順序 ，返回所有從根節點到葉子節點的路徑。
葉子節點 是指沒有子節點的節點。
- 這題用到了回溯，不懂回溯，偷了張圖大概看一下
/**
* 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<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();//結果列表
if(root==null){return res;}
List<Integer> path = new ArrayList<Integer>();//路徑列表（存放經過結點的值）
postOrder(root,path,res);
return res;
}
public void postOrder(TreeNode node,List<Integer> path,List<String> res){
path.add(node.val);//每一個結點都加在路徑裡面
if(node.left==null&&node.right==null){//如果node沒孩子（葉子節點）
//就可以把path轉換成String加到res中啦
StringBuilder sb = new StringBuilder();
for (Integer i : path) {
sb.append(i+"->");
}
String s = sb.toString();
s = s.substring(0,s.length()-2);//把最後一個->去掉
res.add(s);
}
if (node.left != null) {
postOrder(node.left, path, res);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
postOrder(node.right, path, res);
path.remove(path.size()-1);//回溯
}
}
}
- 這題挺好，標記。
404. 左葉子之和
給定二叉樹的根節點 root ，返回所有左葉子之和。
- 這題的突破點是找左葉子的定義：當一個結點的左孩子不空（無所謂右孩子）,且左孩子沒孩子，即為左葉子。
/**
* 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 int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
int midValue = 0;//存儲當前結點的左孩子的值
if(root.left!=null&&root.left.left==null&&root.left.right==null){
midValue = root.left.val;//如果root.left滿足左葉子的條件
}
int leftValue = sumOfLeftLeaves(root.left);
int rightValue = sumOfLeftLeaves(root.right);
return midValue+leftValue+rightValue;//返回當前結點的值，加上左右孩子的葉子結點數
}
}
- 遞歸真的是不好想啊，感覺我現在的水平只能是看懂
513. 找樹左下角的值
給定一個二叉樹的 根節點 root，請找出該二叉樹的 最底層 最左邊 節點的值。
假設二叉樹中至少有一個節點。
ψ(｀∇´)ψ 我的思路
- 層序遍歷到最後一層，第一個彈出的值即為所求
/**
* 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 int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();
List<Integer> list = null;
que.add(root);
while (!que.isEmpty()){//控制層數
list = new ArrayList<>();
int size = que.size();
while (size>0){//控制每層的元素個數
TreeNode node = que.poll();
list.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
if(size==1){
}
size--;
}
}
return list.get(0);//因為鏈表每層都刷新，所以此時鏈表記錄的是最後一層的結點
}
}
- hhh，只要可以用層序遍歷，我就是小神仙🎈
112. 路徑總和
給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum 。判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等於目標和 targetSum 。如果存在，返回 true ；否則，返回 false 。
葉子節點 是指沒有子節點的節點。
- 感覺和上面的二叉樹的所有路徑很像，就改了一下上面的程式碼。第一遍的時候是自己寫的，沒有寫出來。
/**
* 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 hasPathSum(TreeNode root, int targetSum) {
List<Integer> res = new ArrayList<>();//用來存放所有路徑的和
if(root==null){return false;}
List<Integer> path = new ArrayList<Integer>();//用來存放經過結點的值
postOrder(root,path,res);
if(res.contains(targetSum)){return true;}
else return false;
}
public void postOrder(TreeNode node,List<Integer> path,List<Integer> res){
path.add(node.val);//每一個結點的值都加在路徑裡面
if(node.left==null&&node.right==null){//如果node沒孩子（葉子節點）
int sum = 0;
for (Integer i : path) {
sum += i;
}
res.add(sum); //求出當前路徑的總和加到res中
}
if (node.left != null) {
postOrder(node.left, path, res);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
postOrder(node.right, path, res);
path.remove(path.size()-1);//回溯
}
}
}
113. 路徑總和 II
給你二叉樹的根節點 root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等於給定目標和的路徑。
葉子節點 是指沒有子節點的節點。
ψ(｀∇´)ψ 我的思路
- 還是路徑的問題，我就按路徑的模板寫了一下，但是在debug的時候發現res會隨著path的改變而改變。活見鬼👻，我明明已經把path加到res里了。
/**
* 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>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();//結果列表
List<Integer> path = new ArrayList<>();//路徑列表
if(root==null){return res;}
path(root,path,res,targetSum);
return res;
}
void path(TreeNode node,List<Integer> path,List<List<Integer>> res,int targetSum){
path.add(node.val);
if(node.left==null&&node.right==null){//到達了葉子結點
int sum = 0;
for (Integer i : path) {
sum+=i;
}
if(sum==targetSum){res.add(path);}
}
if (node.left != null) {
path(node.left, path, res, targetSum);
path.remove(path.size()-1);//回溯
}
if (node.right != null) {
path(node.right, path, res, targetSum);
path.remove(path.size()-1);//回溯
}
}
}
- 但仔細一想應該是遞歸的問題，我找不到解決的方法，看了題解後發現其實就是一行程式碼
if(sum==targetSum){ res.add(new ArrayList<>(path));}
- 活見鬼👻,剛開始看的時候我就不相信這是java的語法，我就沒見過泛型後面的小括弧裡面放東西😟，但是運行通過。網上也找不到靠譜的解釋，我猜是新建了一個與path相同類型的鏈表把path裝了進來，這樣我再debug，res就不會隨著遞歸變化了。
❗標記，標記，這一題不太會
106. 從中序與後序遍歷序列構造二叉樹
給定兩個整數數組 inorder 和 postorder ，其中 inorder 是二叉樹的中序遍歷， postorder 是同一棵樹的後序遍歷，請你構造並返回這顆 二叉樹 。
確認過眼神，是我寫不出來的題目🙂
- 思路是不難理解的，偷個圖展示一下
步驟：
- 判斷後序數組是否為空
- 取後序數組的最後一個值的下標切割中序數組，把中序數組切割成左中序和右中序
- 用兩個區間的長度去切割後序數組，得到左後序和右後序
- 遞歸（左中序，左後序），遞歸（右中序，右後序）
/**
* 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 {
Map<Integer, Integer> map; // 方便根據數值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的數值對應位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前閉後開
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 參數里的範圍都是前閉後開
if (inBegin >= inEnd || postBegin >= postEnd) { // 不滿足左閉右開，說明沒有元素，返回空樹
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到後序遍歷的最後一個元素在中序遍歷中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 構造結點
int lenOfLeft = rootIndex - inBegin; // 保存中序左子樹個數，用來確定後序數列的個數
root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}
- ❗ 標記，標記，這題不是自己寫的
105. 從前序與中序遍歷序列構造二叉樹
給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹並返回其根節點。
- 與上一題類似，改了一下上一題的程式碼
/**
* 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 {
Map<Integer, Integer> map; // 方便根據數值查找位置
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的數值對應位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, preorder,0, preorder.length); // 前閉後開
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
// 參數里的範圍都是前閉後開
if (inBegin >= inEnd || preBegin >= preEnd) { // 不滿足左閉右開，說明沒有元素，返回空樹
return null;
}
int rootIndex = map.get(preorder[preBegin]); // 找到前序遍歷的最後一個元素在中序遍歷中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 構造結點
int lenOfLeft = rootIndex - inBegin; // 保存中序左子樹個數，用來確定前序數列的個數
root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin+1, preBegin + lenOfLeft+1);
root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft+1, preEnd);
return root;
}
}
- 太殘忍了，太殘忍了，最後這兩題，就是在屠殺我的腦細胞💀，不知道看多少集海綿寶寶才能養回來
總結
-
今天的題比昨天的題要好，每一道題都很有代表性😀
-
翻轉二叉樹：交換結點指向左右孩子的指針
-
對稱二叉樹：以根結點所在豎直線為對稱軸，先比較外側結點，後比較內側結點（相同的樹，另一棵樹的子樹類似）（有點像雙指針
-
二叉樹的最大深度：求二叉樹的最大深度就是求根結點的高度，求高度用後序遍歷，當前結點的高度是左右孩子高度的最大值+1（N叉樹的最大深度類似）
-
二叉樹的最小深度：如果左子樹為空，當前結點的高度為右子樹的高度+1；如果右子樹為空，當前結點的高度為左子樹的高度+1，畫個圖你就知道啦🤡
-
完全二叉樹的結點個數：基礎的遍歷題
-
平衡二叉樹：求高度的題，要用後序遍歷
-
二叉樹的所有路徑：求路徑的題，要用到回溯，需要什麼條件就往遞歸方法中加參數就可
-
左葉子之和：關鍵是判斷左葉子
-
找樹左下角的值：層序遍歷
-
路徑總和：改路徑題的模板（其實還是有點迷的，尤其是遞歸方法帶參數，好傢夥，那是一個千變萬化，根本分析不出來😵）
-
從中/前序後序遍歷序列構造二叉樹，重點在區間的劃分
-
遇到問題總是先想層序遍歷，但是感覺遞歸才是正統解法，要好好掌握遞歸才行
-
做了一天的二叉樹，現在感覺我就是個二叉樹🤐
