二叉树基础知识：可查看http://www.cnblogs.com/polly333/p/4740355.html
层序遍历：依靠队列，没有递归解法。可查看https://www.cnblogs.com/hapjin/p/5409921.html
前中后序遍历：依靠栈，有递归和非递归两种解法
1.求二叉树根到叶节点的最短距离
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
类似maximum-depth-of-binary-tree。不过注意，如果一个节点只有左子树或只有右子树。我们不能取左右子树中最短的，会取到0(叶子节点指的是没有子节点的节点），这样不符合题意。所以二者其一为空时，就取另一个的长度，最为最短长度。
递归解法:
/**
* 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);
}
}
非递归解法：用到了层序遍历。
根节点入队列。
然后在循环中判断队列非空时，弹出队列中的节点，并把节点的子节点入队列。
curNum用来记录一层的节点数。
lastNum记录这层还需要遍历的节点数。当lastNum为0时，说明这层已经遍历完，可以层数+1；
终止条件即为：找到了左右子树都为空的节点。
如果是求maximum-depth，则终止条件是queue为空==》即所有的节点都被遍历过。
/**
* 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;
}
}
要点：
- 递归解法：需要注意判断子节点左右节点其中一个为空的情况
- 非递归解法：用linkedList作为队列；记录层中节点数，遍历完一层，层数+1；
关于LinkedList
- poll()和pop()都是取first并删除，队列为空时前者返回null，后者返回NoSuchElementException。本质都是调用unLinkList()
- offer(),add()都是向队列中添加元素到末尾。offer调了add。返回值为true，实际调用linkLast()。
push是添加元素到开头。实际调用linkFirst()。无返回值
2.求二叉树根到叶节点的最大距离
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不会提前判断叶子节点，叶子节点会走到最后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)
迭代解法
利用两个队列来完成。
要点：对称树实际上是判断左树和右树是否对称。以根节点为中轴线，左边的存入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.打印条件是：没有孩子（最终节点）或者上一个节点是它的孩子（孩子节点打完，需要打印上层节点）
3.放入时从右向左放节点，与读取顺序相反
如果是前序遍历，则不需要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，会遍历到最下面的节点，然后打印。保证先打出来的就是最下层。而且是先遍历到左节点的最下层，才会遍历右节点。
如果是前序遍历，则把 res.add(root.val);提到for循环之前
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.入栈当前节点，并将左子节点置为下个遍历节点。while循环结束时，所有的左子节点都入栈。
3.出栈时，pop节点打印。并将右子节点设为下个遍历节点。
/**
* 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;
}
//取出节点，并把当前节点设成取出节点的右子节点
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/
只取每层的最后一个节点
7.翻转二叉树
https://leetcode-cn.com/problems/invert-binary-tree/description/
递归解法：
1.翻转左右节点
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的方法求树高度。
判断根节点的左右两子树高度差是否大于1，若大于1则非平衡树，返回false;否则，继续递归的判断其左子树和右子树是否是平衡树。
这样做会重复遍历多次节点。求一个节点的深度是O(lgn)，所以求所有节点的就是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;
}
}
上面那个方法正确但不是很高效，因为每一个点都会被上面的点计算深度时访问一次，我们可以进行优化。方法是如果我们发现子树不平衡，则不计算具体的深度，而是直接返回-1。那么优化后的方法为：对于每一个节点，我们通过checkDepth方法递归获得左右子树的深度，如果子树是平衡的，则返回真实的深度，若不平衡，直接返回-1，此方法时间复杂度O(N)，空间复杂度O(H)，参见代码如下：
要点在于计算高度的时候顺便算出是否平衡，同一个节点不需要遍历两次
/**
* 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，保留这个节点。对其左右节点进行剪枝
2.如果左右节点剪枝不为空，那么保留这个节点
3.如果左右节点剪枝为空，说明节点为0，左右节点剪枝结果为null，不保留这个节点
/**
* 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.将有序数组转化为二叉搜索树
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-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 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的值，左右节点分别是左右子树的剪枝结果
/**
* 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;
}
}
}
