這篇文章總結了一下這兩天刷的二叉樹的解題方法徒欣，主要是遞歸、迭代的DFS相速、迭代的BSF這三種秩彤。題目列表如下：
題目列表
101 二叉樹的最大深度
111 二叉樹的最小深度
110 平衡二叉樹
108 將有序數(shù)組轉換為二叉搜索樹
112 路徑總和
226 翻轉二叉樹
257 二叉樹的所有路徑
235 二叉搜索樹的最近公共祖先
404 左葉子之和
101 二叉樹的最大深度
題目大意
給定一個二叉樹，找出其最大深度览徒。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)狈定。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例：
給定二叉樹 [3,9,20,null,null,15,7]习蓬，返回它的最大深度3纽什。
解法一：遞歸
思考遞歸解法時，想清楚三個問題：
1.返回條件是什么躲叼？
答：在此題中芦缰，如果根節(jié)點是個空結點，返回高度0枫慷。
2.遞歸返回的是什么让蕾？
答：返回樹的高度浪规。
直接來看看遞歸程序。
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
解法二：DFS
DFS需要借助棧來實現(xiàn)探孝，這里我們設置兩個棧笋婿，一個操作結點，一個記錄每個結點的層數(shù)顿颅。每當我們將一個結點的左右孩子入棧缸濒，其左右孩子的層數(shù)就會在父節(jié)點層數(shù)的基礎上加一。
public static int maxDepth(TreeNode root) {
if(root==null) return 0;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> value = new Stack<>(); //保存層數(shù)
stack.push(root); //根節(jié)點加入stack
value.push(1);
int depth = 1;
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
int cur= value.pop(); //當前結點的層數(shù)
depth = depth>cur?depth:cur;
if(p.left!=null) {
stack.push(p.left);
value.push(cur+1);
}
if(p.right!=null) {
stack.push(p.right);
value.push(cur+1);
}
}
return depth;
}
解法三：BFS
廣度優(yōu)先搜索借助隊列完成粱腻，它可以實現(xiàn)層次遍歷庇配。每次彈出一個元素，就要將它的左右孩子入隊栖疑。直至隊列為空讨永。
public static int maxDepth(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int depth = 0;
while(!que.isEmpty()) {
int size = que.size(); //上一層遺留了多少結點
++depth;
for(int i=0;i<size;++i) { //將上一層的結點全部出隊
TreeNode node = que.poll();
if(node.left!=null) //左節(jié)點入隊
que.offer(node.left);
if(node.right!=null) //右節(jié)點入隊
que.offer(node.right);
}
}
return depth;
}
111 二叉樹的最小深度
題目大意
給定一個二叉樹，找出其最小深度遇革。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量卿闹。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例：
給定二叉樹 [3,9,20,null,null,15,7]萝快，返回它的最小深度 2锻霎。
思路
這一題和求二叉樹的高度類似，有遞歸揪漩、DFS旋恼、BFS三種常用解法。需要隨時更新當前最小的depth奄容。
解法一：遞歸
public int minDepth(TreeNode root) {
if(root==null) return 0;
if(root.left == null && root.right == null) return 1;
int cur_min_depth = Integer.MAX_VALUE;
if(root.left!=null) cur_min_depth = Math.min(minDepth(root.left),cur_min_depth);
if(root.right!=null) cur_min_depth = Math.min(minDepth(root.right),cur_min_depth);
return cur_min_depth+1;
}
運行時間1ms冰更。
解法二：BFS
層次遍歷，當訪問到第一個葉子結點就可以結束算法昂勒，返回最小的高度蜀细。
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue <TreeNode> que = new LinkedList<>();
que.offer(root);
int ans = 0;
while(!que.isEmpty()) {
++ans; //這一層的層數(shù)
int size = que.size();
for(int i=0;i<size;i++) {
TreeNode p = que.poll();
if(p.left == null && p.right==null) //葉子結點
return ans;
if(p.left!=null) que.offer(p.left);
if(p.right!=null) que.offer(p.right);
}
}
return ans;
}
運行時間1ms。
解法三：DFS
依舊用兩個棧戈盈，一個記錄結點奠衔，一個記錄層數(shù)，還有一個min_depth變量塘娶，隨時更新當前最小的層數(shù)归斤。
public int minDepth(TreeNode root) {
if(root == null) return 0;
Stack <TreeNode> stack = new Stack<>();
Stack <Integer> value = new Stack<>();
stack.push(root);
value.push(1);
int min_depth = Integer.MAX_VALUE;
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
int temp = value.pop();
if(p.left == null && p.right == null) min_depth= Math.min(temp,min_depth);
if(p.left!=null) {
stack.push(p.left);
value.push(temp+1);
}
if(p.right!=null) {
stack.push(p.right);
value.push(temp+1);
}
}
return min_depth;
}
解法四
這個解法將單支樹的情況做了特殊考慮驶兜。
public static int minDepth(TreeNode root) {
//1.根節(jié)點為空
if(root==null) return 0;
//2.根節(jié)點左右孩子為空
if(root.left==null && root.right==null) return 1;
int left = minDepth(root.left);
int right = minDepth(root.right);
//3.單枝樹
if(root.left==null || root.right==null) return left+right+1;
//4.非單枝樹
return Math.min(left,right)+1;
}
110 平衡二叉樹
題目大意
給定一個二叉樹颜启，判斷它是否是高度平衡的二叉樹。
本題中球切，一棵高度平衡二叉樹定義為：
一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過1虹曙。
示例：
給定二叉樹 [3,9,20,null,null,15,7]膝宁，返回 true 鸦难。
解法一：遞歸(自頂向下)
判斷一棵樹是否平衡的流程為，首先根節(jié)點平衡嗎员淫？若平衡，判斷它的左击敌、右子樹是否都平衡介返。算法應該包含一個求子樹高度的函數(shù)height。
private int height(TreeNode root) {
if(root == null) return 0;
return Math.max(height(root.left),height(root.right))+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return isBalanced(root.left) && isBalanced(root.right) &&
(Math.abs(height(root.left)-height(root.right))<=1);
}
運行時間3ms沃斤。
解法二：自底向上圣蝎，遞歸。
在求子樹高度時衡瓶，如果發(fā)現(xiàn)任何一棵子樹打破了平衡徘公，馬上返回-1終止算法。
public boolean isBalanced(TreeNode root) {
int res = height(root); //求樹所有葉子的高度
return res==-1?false:true;
}
private int height(TreeNode root) {
if(root == null) return 0;
int heightOfLeft = height(root.left);
if(heightOfLeft == -1) return -1;
int heightOfRight = height(root.right);
if(heightOfRight == -1) return -1;
if(Math.abs(heightOfLeft-heightOfRight)>1) return -1;
return Math.max(heightOfLeft,heightOfRight)+1;
}
運行時間3ms哮针。
解法三：設置全局變量
很好理解关面，直接看代碼吧。
public boolean isBalanced(TreeNode root) {
height(root); //求樹所有葉子的高度
return res;
}
boolean res = true;
private int height(TreeNode root) {
if(root == null ||!res) return 0;
int left = height(root.left);
int right = height(root.right);
if(Math.abs(left-right)>1) res = false;
return Math.max(left,right)+1;
}
運行時間2ms十厢。
108 將有序數(shù)組轉換為二叉搜索樹
題目大意
將一個按照升序排列的有序數(shù)組等太，轉換為一棵高度平衡二叉搜索樹。
本題中蛮放，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1缩抡。
示例：
給定有序數(shù)組: [-10,-3,0,5,9],
一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：
思路
因為給出的數(shù)組有序包颁，此題類似于二分法解法瞻想，每次取中間的數(shù)mid作為根節(jié)點，小于mid的部分劃分為左子樹娩嚼，大于mid的部分劃分為右子樹蘑险。
public TreeNode sortedArrayToBST(int[] nums) {
return createBST(nums,0,nums.length-1);
}
public TreeNode createBST(int[] nums,int low,int high) {
if(low>high) return null; //注意遞歸的結束條件(low>high)
int mid = (low+high) >>>1;
TreeNode root = new TreeNode(nums[mid]);
root.left = createBST(nums,low,mid-1);
root.right = createBST(nums,mid+1,high);
return root;
}
112 路徑總和
題目大意
給定一個二叉樹和一個目標和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑待锈，這條路徑上所有節(jié)點值相加等于目標和漠其。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例：
給定如下二叉樹竿音，以及目標和 sum = 22和屎，返回 true, 因為存在目標和為 22 的根節(jié)點到葉子節(jié)點的路徑 5->4->11->2。
解法一：遞歸
這一版是自己寫的遞歸程序春瞬，寫的比較繁瑣柴信，但是理解上應該沒問題。之后會貼上優(yōu)化后的版本宽气。
public boolean hasPathSum(TreeNode root, int sum) {
findPath(root,sum);
return flag;
}
private boolean findPath(TreeNode root, int sum) {
if(root == null) return false;
if(root.val == sum && root.left == null && root.right == null) {
flag = true;
return true;
}
if(root.left!=null) findPath(root.left,sum-root.val);
if(flag) return true;
if(root.right!=null) findPath(root.right,sum-root.val);
if(flag) return true;
return false;
}
未優(yōu)化版本随常，運行時間2ms潜沦。接下來來看評論區(qū)的優(yōu)化版本。
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
sum -= root.val;
if(root.left==null && root.right==null) return sum==0;
return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
}
解法二：DFS
利用兩個棧绪氛，一個存儲結點唆鸡，一個存儲剩余的路徑長度。
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null) return false;
Stack<TreeNode> node = new Stack<>();
Stack<Integer> num = new Stack<>();
node.push(root);
num.push(sum-root.val); //剩余路徑
while(!node.isEmpty()) {
TreeNode p = node.pop();
int path = num.pop();
if(path==0 && p.left==null && p.right==null) return true;
if(p.left!=null) {
node.push(p.left);
num.push(path-p.left.val);
}
if(p.right!=null) {
node.push(p.right);
num.push(path-p.right.val);
}
}
return false;
}
226 翻轉二叉樹
題目大意
翻轉一棵二叉樹枣察。
示例:
輸入：
輸出：
方法一：遞歸
遞歸結束的條件為該節(jié)點為null或者該節(jié)點的左右孩子為空争占。
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
if(root.left==null && root.right == null) return root;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
運行時間1ms,擊敗89.13%。
方法二：迭代
利用層序遍歷序目，交換每一個節(jié)點的左右節(jié)點臂痕。當poll的時候，進行交換操作猿涨。
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()) {
TreeNode cur = que.poll();
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
if(cur.left!=null) que.offer(cur.left);
if(cur.right!=null) que.offer(cur.right);
}
return root;
}
運行時間1ms,擊敗89.09%握童。
257 二叉樹的所有路徑
題目大意
給定一個二叉樹，返回所有從根節(jié)點到葉子節(jié)點的路徑叛赚。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點澡绩。
示例：
方法一：遞歸
題目給出的函數(shù)返回List,在遍歷樹的時候，需要利用String path存儲路徑红伦，遍歷時采用先序遍歷的方式英古，每次訪問一個結點，就將它拼接到path字符串中昙读。當該結點沒有左右孩子的時候召调，一條完整path生成，將它加入list中蛮浑。
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
if(root==null) return list;
findPath(root,list,"");
return list;
}
private void findPath(TreeNode root,List list,String path) {
path += root.val+" ";
if(root.left==null && root.right==null) {
list.add(path.trim().replace(" ","->"));
}
if(root.left!=null)
findPath(root.left,list,path);
if(root.right!=null)
findPath(root.right,list,path);
}
運行時間14ms,擊敗6.7%唠叛。
方法二：迭代
迭代方法中利用兩個棧結構，一個存儲遍歷的node沮稚，另一個存儲path艺沼。直接通過代碼理解。
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList<>();
if(root==null) return res;
LinkedList<TreeNode> nodes = new LinkedList<>();
LinkedList<String> paths = new LinkedList<>();
nodes.add(root);
paths.add(Integer.toString(root.val));
TreeNode node;
String path;
while(!nodes.isEmpty()) {
node = nodes.pollLast();
path = paths.pollLast();
if(node.left==null && node.right == null)
res.add(path);
if(node.left!=null) {
nodes.add(node.left);
paths.add(path+"->"+Integer.toString(node.left.val));
}
if(node.right!=null) {
nodes.add(node.right);
paths.add(path+"->"+Integer.toString(node.right.val));
}
}
return res;
}
}
運行時間3ms,擊敗91.68%蕴掏。
235 二叉搜索樹的最近公共祖先
題目大意
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先障般。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q盛杰，最近公共祖先表示為一個結點 x挽荡，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）即供《猓”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例1：
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6逗嫡。
示例2：
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身青自。
說明：
所有節(jié)點的值都是唯一的株依。
p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中延窜。
方法一：遞歸
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(root.val>p.val && root.val > q.val)
return lowestCommonAncestor(root.left,p,q);
else if(root.val<p.val && root.val<q.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
運行時間11ms恋腕，擊敗72.19%。
方法二：迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
while(root!=null) {
if(root.val>p.val && root.val > q.val)
root = root.left;
else if(root.val < q.val && root.val < p.val)
root = root.right;
else
return root;
}
return root;
}
運行時間12ms,擊敗37.02%逆瑞。
404 左葉子之和
題目大意
計算給定二叉樹的所有左葉子之和吗坚。
示例：
在這個二叉樹中，有兩個左葉子呆万，分別是 9 和 15，所以返回 24
方法一：棧
利用棧车份，遍歷整個二叉樹谋减，并且對每個結點判斷是否為左葉子。
public int sumOfLeftLeaves(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if (root==null) return 0;
int res = 0;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode t = stack.pop();
if(t.left!=null) stack.push(t.left);
if(t.right!=null) stack.push(t.right);
if(t.left!=null && t.left.left==null && t.left.right==null) res+=t.left.val;
}
return res;
}
運行時間2ms扫沼，擊敗15.56%出爹。
方法二：遞歸
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
if(root.left!=null && root.left.left==null && root.left.right==null)
return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
}
運行時間0ms,擊敗100%。
