二叉樹基礎知識：可查看http://www.cnblogs.com/polly333/p/4740355.html
層序遍歷：依靠隊列睁壁，沒有遞歸解法为狸〖吖可查看https://www.cnblogs.com/hapjin/p/5409921.html
前中后序遍歷：依靠棧，有遞歸和非遞歸兩種解法
1.求二叉樹根到葉節(jié)點的最短距離
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
類似maximum-depth-of-binary-tree辐棒。不過注意病曾，如果一個節(jié)點只有左子樹或只有右子樹。我們不能取左右子樹中最短的漾根，會取到0(葉子節(jié)點指的是沒有子節(jié)點的節(jié)點）泰涂，這樣不符合題意。所以二者其一為空時辐怕，就取另一個的長度逼蒙，最為最短長度。
遞歸解法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null){
return minDepth(root.right)+1;
}
if(root.right==null){
return minDepth(root.left)+1;
}
return Math.min(minDepth(root.right)+1,minDepth(root.left)+1);
}
}
非遞歸解法：用到了層序遍歷秘蛇。
根節(jié)點入隊列其做。
然后在循環(huán)中判斷隊列非空時，彈出隊列中的節(jié)點赁还，并把節(jié)點的子節(jié)點入隊列妖泄。
curNum用來記錄一層的節(jié)點數(shù)。
lastNum記錄這層還需要遍歷的節(jié)點數(shù)艘策。當lastNum為0時蹈胡，說明這層已經(jīng)遍歷完，可以層數(shù)+1朋蔫；
終止條件即為：找到了左右子樹都為空的節(jié)點罚渐。
如果是求maximum-depth，則終止條件是queue為空==》即所有的節(jié)點都被遍歷過驯妄。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null)return 0;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int curNum = 0;
int lastNum=1;
int level=1荷并；
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
lastNum--;
if(temp.left==null&&temp.right==null){
return level;
}
if(temp.left!=null){
queue.add(temp.left);
curNum++;
}
if(temp.right!=null){
queue.add(temp.right);
curNum++;
}
if(lastNum==0){
lastNum=curNum;
curNum=0;
level++;
}
}
return 0;
}
}
要點：
- 遞歸解法：需要注意判斷子節(jié)點左右節(jié)點其中一個為空的情況
- 非遞歸解法：用linkedList作為隊列；記錄層中節(jié)點數(shù)青扔，遍歷完一層源织，層數(shù)+1翩伪；
關于LinkedList
- poll()和pop()都是取first并刪除，隊列為空時前者返回null谈息，后者返回NoSuchElementException缘屹。本質都是調用unLinkList()
- offer(),add()都是向隊列中添加元素到末尾。offer調了add侠仇。返回值為true轻姿，實際調用linkLast()。
push是添加元素到開頭逻炊。實際調用linkFirst()互亮。無返回值
2.求二叉樹根到葉節(jié)點的最大距離
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/
非遞歸解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)return 0;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int curNum=0;
int lastNum=1;
int level =0;
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
lastNum--;
if(temp.left!=null){
queue.add(temp.left);
curNum++;
}
if(temp.right!=null){
queue.add(temp.right);
curNum++;
}
if(lastNum==0){
lastNum=curNum;
curNum=0;
level++;
}
}
return level;
}
}
要點：這次的level初始值為0。原因就在于max不會提前判斷葉子節(jié)點嗅骄，葉子節(jié)點會走到最后level++的里面胳挎，所以不需要直接+1
3.對稱二叉樹的判斷
https://leetcode-cn.com/problems/symmetric-tree/description/
遞歸解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)return true;
return ST(root.left,root.right);
}
private boolean ST(TreeNode left,TreeNode right){
if(left==null&&right==null)return true;
else if(left==null||right==null)return false;
else if(left.val!=right.val)return false;
else{
return ST(left.left,right.right)&&ST(left.right,right.left);
}
}
}
要點：遞歸式在于左樹的左孩子和右樹的右孩子判對稱饼疙；左樹的右孩子和右樹的左孩子判對稱溺森。終止條件在于兩邊孩子都是null的時候，left.val=right.val即返回true窑眯。
時間復雜度： 本質其實就是DFS,時間復雜度為O(n)
空間復雜度： O(h)
迭代解法
利用兩個隊列來完成屏积。
要點：對稱樹實際上是判斷左樹和右樹是否對稱。以根節(jié)點為中軸線磅甩，左邊的存入leftQueue,右邊的存入rightQueue炊林；存入順序記得對稱，一一進行比對
注意：此處不能直接左右為空返回true卷要，因為需要進一步的判斷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)return true;
return ST(root);
}
private boolean ST(TreeNode root){
if(root==null)return true;
LinkedList<TreeNode> leftQueue=new LinkedList<TreeNode>();
LinkedList<TreeNode> rightQueue=new LinkedList<TreeNode>();
leftQueue.add(root.left);
rightQueue.add(root.right);
while(!leftQueue.isEmpty()&&!rightQueue.isEmpty()){
TreeNode left=leftQueue.poll();
TreeNode right=rightQueue.poll();
if(left==null&&right==null)continue;
else if(left==null&&right!=null||right==null&&left!=null)return false;
else if(left.val!=right.val)return false;
else{
leftQueue.add(left.left);
leftQueue.add(left.right);
rightQueue.add(right.right);
rightQueue.add(right.left);
}
}
return true;
}
}
4.N叉樹后序遍歷
迭代解法：
1.用棧
2.打印條件是：沒有孩子（最終節(jié)點）或者上一個節(jié)點是它的孩子（孩子節(jié)點打完渣聚，需要打印上層節(jié)點）
3.放入時從右向左放節(jié)點，與讀取順序相反
如果是前序遍歷僧叉，則不需要if判斷奕枝，直接pop打印即可
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> resultList = new LinkedList<Integer>();
if(root==null)return resultList;
Stack<Node> stack =new Stack<Node>();
stack.push(root);
Node pre=null;
Node cur=null;
while(!stack.isEmpty()){
cur = stack.peek();
if(pre!=null && cur.children.contains(pre) || cur.children.isEmpty()){
resultList.add(cur.val);
stack.pop();
pre=cur;
}else{
int length=cur.children.size();
for(int i=0;i<cur.children.size();i++){
stack.push(cur.children.get(length-i-1));
}
}
}
return resultList;
}
}
遞歸解法
dfs，會遍歷到最下面的節(jié)點瓶堕，然后打印隘道。保證先打出來的就是最下層。而且是先遍歷到左節(jié)點的最下層郎笆，才會遍歷右節(jié)點谭梗。
如果是前序遍歷，則把 res.add(root.val);提到for循環(huán)之前
class Solution {
public void dfs(List<Integer> res,Node root){
if(root==null){
return;
}
for(Node x:root.children){
dfs(res,x);
}
res.add(root.val);
}
public List<Integer> postorder(Node root) {
List<Integer> res = new ArrayList<Integer>();
dfs(res,root);
return res;
}
}
5.中序遍歷
要點：
1.使用棧
2.入棧當前節(jié)點宛蚓，并將左子節(jié)點置為下個遍歷節(jié)點激捏。while循環(huán)結束時，所有的左子節(jié)點都入棧凄吏。
3.出棧時远舅，pop節(jié)點打印壹置。并將右子節(jié)點設為下個遍歷節(jié)點。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> res = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root==null)return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur=root;
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
//取出節(jié)點表谊，并把當前節(jié)點設成取出節(jié)點的右子節(jié)點
if(!stack.isEmpty()){
cur=stack.pop();
res.add(cur.val);
cur=cur.right;
}
}
return res;
}
}
6.層次遍歷
遞歸方式
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
set(root, 0, result);
return result;
}
public void set(TreeNode treeNode, int level, List<List<Integer>> result) {
if(treeNode==null){
return;
}
if(level==result.size()){
result.add(new ArrayList<>());
}
result.get(level).add(treeNode.val);
set(treeNode.left,level+1,result);
set(treeNode.right,level+1,result);
}
}
非遞歸方式
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> res = new LinkedList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
if(root==null)return res;
queue.add(root);
int curNum=0;
int lastNum=1;
while(!queue.isEmpty()){
List<Integer> tempList = new LinkedList<Integer>();
while(lastNum!=0){
TreeNode temp = queue.pop();
tempList.add(temp.val);
if(temp.left!=null){
queue.add(temp.left);
curNum++;
}
if(temp.right!=null){
queue.add(temp.right);
curNum++;
}
lastNum--;
}
lastNum=curNum;
curNum=0;
res.add(tempList);
}
return res;
}
}
變形題：二叉樹的右視圖
https://leetcode-cn.com/problems/binary-tree-right-side-view/description/
只取每層的最后一個節(jié)點
7.翻轉二叉樹
https://leetcode-cn.com/problems/invert-binary-tree/description/
遞歸解法：
1.翻轉左右節(jié)點
2.翻轉左右子樹
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)return null;
TreeNode temp=root.right;
root.right=root.left;
root.left=temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
8.平衡二叉樹的判斷
遞歸方式：
用maximum-depth的方法求樹高度钞护。
判斷根節(jié)點的左右兩子樹高度差是否大于1，若大于1則非平衡樹爆办，返回false;否則难咕，繼續(xù)遞歸的判斷其左子樹和右子樹是否是平衡樹。
這樣做會重復遍歷多次節(jié)點距辆。求一個節(jié)點的深度是O(lgn)余佃，所以求所有節(jié)點的就是O(nlgn)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)return true;
int left = treeDepth(root.left);
int right = treeDepth(root.right);
if(Math.abs(left-right)>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);
}
private int treeDepth(TreeNode root){
if(root==null)return 0;
int left = treeDepth(root.left);
int right= treeDepth(root.right);
return Math.max(left,right)+1;
}
}
上面那個方法正確但不是很高效跨算，因為每一個點都會被上面的點計算深度時訪問一次爆土，我們可以進行優(yōu)化。方法是如果我們發(fā)現(xiàn)子樹不平衡诸蚕，則不計算具體的深度步势，而是直接返回-1。那么優(yōu)化后的方法為：對于每一個節(jié)點背犯，我們通過checkDepth方法遞歸獲得左右子樹的深度坏瘩，如果子樹是平衡的，則返回真實的深度漠魏，若不平衡倔矾，直接返回-1，此方法時間復雜度O(N)柱锹，空間復雜度O(H)哪自，參見代碼如下：
要點在于計算高度的時候順便算出是否平衡，同一個節(jié)點不需要遍歷兩次
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
int height = checkDepth(root);
if(height>=0){
return true;
}else{
return false;
}
}
private int checkDepth(TreeNode root){
if(root==null)return 0;
int left = checkDepth(root.left);
int right= checkDepth(root.right);
if(left==-1||right==-1)return -1;
if(Math.abs(left-right)>1){
return -1;
}else{
return Math.max(left,right)+1;
}
}
}
9.二叉樹剪枝
https://leetcode-cn.com/problems/binary-tree-pruning/description/
思路：
1.如果本身為1禁熏，保留這個節(jié)點壤巷。對其左右節(jié)點進行剪枝
2.如果左右節(jié)點剪枝不為空，那么保留這個節(jié)點
3.如果左右節(jié)點剪枝為空匹层，說明節(jié)點為0隙笆，左右節(jié)點剪枝結果為null，不保留這個節(jié)點
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode pruneTree(TreeNode root) {
if(root==null)return null;
TreeNode newRoot;
TreeNode left = pruneTree(root.left);
TreeNode right = pruneTree(root.right);
if(root.val==1){
newRoot = new TreeNode(root.val);
newRoot.left = left;
newRoot.right= right;
}else if(left!=null||right!=null){
newRoot = new TreeNode(root.val);
newRoot.left = left;
newRoot.right= right;
}else{
newRoot=null;
}
return newRoot;
}
}
二叉搜索樹
https://blog.csdn.net/qq_37887537/article/details/75647670
1.將有序數(shù)組轉化為二叉搜索樹
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/description/
二叉搜索樹按照中序遍歷可得到有序數(shù)組升筏；那么反之撑柔，我們可以得知，根節(jié)點是有序數(shù)組的中間節(jié)點您访，從中間節(jié)點分開左右兩個有序數(shù)組铅忿，這兩個有序數(shù)組的中間節(jié)點又分別為中間節(jié)點的左右子節(jié)點。這就是二分查找的中心思想啊灵汪。
思路：
用二分查找法檀训，找到根節(jié)點柑潦，然后左子節(jié)點為左區(qū)間的中間節(jié)點；右子節(jié)點為右區(qū)間的中間節(jié)點峻凫。遞歸而成
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return midSortToBST(nums,0,nums.length-1);
}
private TreeNode midSortToBST(int[] nums,int left,int right){
if(left>right)return null;
int mid = (left+right)/2;
TreeNode cur = new TreeNode(nums[mid]);
cur.left = midSortToBST(nums,left,mid-1);
cur.right = midSortToBST(nums,mid+1,right);
return cur;
}
}
2.二叉搜索樹剪枝
https://leetcode-cn.com/problems/trim-a-binary-search-tree/description/
二叉搜索樹不一定是平衡樹渗鬼。
思路：
1.如果root值小于L，則拋棄左子樹荧琼，返回右子樹的剪枝結果
2.如果root值大于R譬胎，則拋棄右子樹，返回左子樹的剪枝結果
3.如果root值介于L與R之間命锄，則根為root的值堰乔，左右節(jié)點分別是左右子樹的剪枝結果
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root==null)return null;
if(root.val<L){
return trimBST(root.right,L,R);
}else if(root.val>R){
return trimBST(root.left,L,R);
}else{
TreeNode cur = new TreeNode(root.val);
cur.left = trimBST(root.left,L,R);
cur.right = trimBST(root.right,L,R);
return cur;
}
}
}
