網上沖浪的時候，偶然看到科學刷leetcode算法題的方法--算法模版,實踐是檢驗真理的唯一標準，我決定按照他的方法試一試，他這個上面是go語言實現(xiàn)的，我用Java跑一遍試試。
先簡單寫一下，大致列一下，周末時間來完成這個，完成后刪除這句話
二叉樹
1.我的二叉樹的代碼:
二叉樹節(jié)點
package data.structure.binarytree.model;
/**
* 二叉樹的節(jié)點數據結構
*/
public class TreeNode {
//值
private int value;
//左孩子
private TreeNode leftChild;
//右孩子
private TreeNode rightChild;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode(int value) {
this.value = value;
}
}
二叉樹：
package data.structure.binarytree.model;
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree {
//根結點
private TreeNode root=null;
public BinaryTree(){}
public BinaryTree(TreeNode root) {
this.root = root;
}
/**
* 清除子樹
*/
public void clear(TreeNode node){
if (node !=null){
clear(node.getLeftChild());
clear(node.getRightChild());
node = null;//清除節(jié)點
}
}
/**
* 清除根結點
*/
public void clear(){
clear(root);
}
/**
* 判斷是否為空
*/
public boolean isEmpty(){
return root == null;
}
/**
* (遞歸)獲取以某節(jié)點的樹高（DFS)
* @param node
* @return
*/
public int hightRecursion(TreeNode node){
if (node == null){
return 0;//當前節(jié)點為null則樹高為0
}else{
int l = hightRecursion(node.getLeftChild());//遞歸獲取左子樹的樹高
int r = hightRecursion(node.getRightChild());//遞歸獲取右子樹的樹高
return l > r? (l+1) : (r+1);//左右子樹高的為樹高+自身這一層
}
}
/**
* (非遞歸)獲取以某節(jié)點的樹高（BFS）
* @param node
* @return
*/
public int hight(TreeNode node){
if (node == null){
return 0;//當前節(jié)點為null則樹高為0
}
int treeHight = 0;
Queue<TreeNode> tempNode = new LinkedList<>();
tempNode.offer(node);
while (!tempNode.isEmpty()){
int count = tempNode.size();
while (count > 0){
node = tempNode.poll();
if (node.getLeftChild() != null){
tempNode.offer(node.getLeftChild());
}
if (node.getRightChild() != null){
tempNode.offer(node.getRightChild());
}
count--;
}
treeHight++;
}
return treeHight;
}
/**
* 獲取樹高
* @return
*/
public int hight(){
return hight(root);
}
/**
* 獲取某子數的節(jié)點數
* @param node
* @return
*/
public int size(TreeNode node){
if (node == null){
return 0;//當前節(jié)點為null則節(jié)點數為0
}else{
//當前節(jié)點+左子樹節(jié)點數+右子樹節(jié)點數
return 1 + size(node.getLeftChild())+size(node.getRightChild());
}
}
/**
* 當前樹的節(jié)點數
* @return
*/
public int size(){
return size(root);
}
/**
* 尋找某節(jié)點在某子樹中的父親節(jié)點（還可以在node中增加parent字段來解決）
* @param subTree
* @param node
* @return
*/
public TreeNode getParent(TreeNode subTree, TreeNode node){
if (subTree == null){
return null;//子樹為null
}
if (subTree.getLeftChild() == node || subTree.getRightChild() == node){
return subTree;
}
TreeNode parent;
parent = getParent(subTree.getLeftChild(),node);//從左子樹中找尋
if (parent != null){
return parent;
}
parent = getParent(subTree.getRightChild(), node);//從右子樹找尋
return parent;
}
/**
* 從樹中找節(jié)點的父節(jié)點
* @param node
* @return
*/
public TreeNode getParent(TreeNode node){
return getParent(root,node);
}
/**
* 是否是平衡二叉樹
* @param node
* @return
*/
public boolean isBalanced(TreeNode node){
int hight = higthForBalance(root);
if ( hight >= 0){
return true;
}
return false;
}
/**
* 自底向上判斷，如果存在而左右子樹樹高相差大于1的則是不平衡，最后輸出-1；如果是平衡的，則是正常樹高>=0
* @param node
* @return
*/
private int higthForBalance(TreeNode node){
if (node == null){
return 0;
}
int leftHight = higthForBalance(node.getLeftChild());
int rightHight = higthForBalance(node.getRightChild());
if (leftHight == -1 || rightHight == -1 || Math.abs(leftHight-rightHight) >1){
return -1;
}else {
return leftHight > rightHight ?(leftHight+1) : (rightHight+1);
}
}
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
}
二叉樹相關的遍歷
package data.structure.binarytree.algorithm;
import data.structure.binarytree.model.BinaryTree;
import data.structure.binarytree.model.TreeNode;
import java.util.*;
public class BinaryTreeTraversal {
/**
* 先序遍歷（遞歸） 根結點 ---> 左子樹 ---> 右子樹
*
* @param root
*/
public void preorderTraversalRecursion(TreeNode root) {
if (root != null) {
System.out.println(root.getValue() + " ");
preorderTraversalRecursion(root.getLeftChild());
preorderTraversalRecursion(root.getRightChild());
}
}
/**
* 先序遍歷（非遞歸） 根結點 ---> 左子樹 ---> 右子樹
*
* @param root
*/
public void preorderTraversal(TreeNode root) {
Stack<TreeNode> tempNode = new Stack<>();
TreeNode currentNode = root;
while (currentNode != null || !tempNode.isEmpty()) {
//左子樹
while (currentNode != null) {
System.out.println(currentNode.getValue());
tempNode.push(currentNode);
currentNode = currentNode.getLeftChild();
}
//右子樹
currentNode = tempNode.pop().getRightChild();
}
}
/**
* 中序遍歷（遞歸） 左子樹---> 根結點 ---> 右子樹
*
* @param root
*/
public void inorderTraversalRecursion(TreeNode root) {
if (root != null) {
inorderTraversalRecursion(root.getLeftChild());
System.out.println(root.getValue() + " ");
inorderTraversalRecursion(root.getRightChild());
}
}
/**
* 中序遍歷（遞歸） 左子樹---> 根結點 ---> 右子樹
*
* @param root
*/
public void inorderTraversal(TreeNode root) {
Stack<TreeNode> tempNode = new Stack<>();
TreeNode currentNode = root;
while (currentNode != null || !tempNode.isEmpty()) {
while (currentNode != null) {
tempNode.push(currentNode);
currentNode = currentNode.getLeftChild();
}
TreeNode popNode = tempNode.pop();
System.out.println(popNode.getValue());
currentNode = popNode.getRightChild();
}
}
/**
* 后序遍歷（遞歸） 左子樹 ---> 右子樹 ---> 根結點
*
* @param root
*/
public void postorderTraversalRecursion(TreeNode root) {
if (root != null) {
postorderTraversalRecursion(root.getLeftChild());
postorderTraversalRecursion(root.getRightChild());
System.out.println(root.getValue() + " ");
}
}
/**
* 后序遍歷（非遞歸） 左子樹 ---> 右子樹 ---> 根結點
*
* @param root
*/
public static void postorderTraversal(TreeNode root) {
Stack<TreeNode> tempNode = new Stack<>();
TreeNode currentNode = root;
TreeNode preNode = null;
while (currentNode != null || !tempNode.isEmpty()) {
//左子樹
while (currentNode != null) {
tempNode.push(currentNode);
currentNode = currentNode.getLeftChild();
}
TreeNode popNode = tempNode.pop();
currentNode = popNode.getRightChild();
//當前節(jié)點右子樹不為空（1.還未遍歷右子樹；2.已經遍歷過右子樹了，通過preNode是否與當前右子樹根結點相同來判斷）
if (currentNode != null && preNode != popNode.getRightChild()) {
tempNode.push(popNode);
} else {
System.out.println(popNode.getValue());
//記錄打印的值
preNode = popNode;
currentNode = null;
}
}
}
/**
* 后序遍歷（遞歸） 左子樹 ---> 右子樹 ---> 根結點
*
* @param root
*/
public void maxPathNum(TreeNode root) {
if (root != null) {
maxPathNum(root.getLeftChild());
maxPathNum(root.getRightChild());
System.out.println(root.getValue());
}
}
private int maxSum = Integer.MIN_VALUE;
/**
* 給你一個二叉樹的根節(jié)點 root ，返回其最大路徑和。
*
* @param root
* @return
*/
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 遞歸計算左右子節(jié)點的最大貢獻值
// 只有在最大貢獻值大于 0 時，才會選取對應子節(jié)點
int leftGain = Math.max(maxGain(node.getLeftChild()), 0);
int rightGain = Math.max(maxGain(node.getRightChild()), 0);
// 節(jié)點的最大路徑和取決于該節(jié)點的值與該節(jié)點的左右子節(jié)點的最大貢獻值
int priceNewpath = node.getValue() + leftGain + rightGain;
// 更新答案
maxSum = Math.max(maxSum, priceNewpath);
// 返回節(jié)點的最大貢獻值（只能選擇一邊，對于它的父節(jié)點而言，這條路徑要么經過當前節(jié)點的左孩子，要么經過右孩子）
return node.getValue() + Math.max(leftGain, rightGain);
}
// public int maxPathSum2(TreeNode root) {
// int result = maxPathSumCount(root);
// return Math.max(maxSum,result);
// }
//
// public int maxPathSumCount(TreeNode root) {
// if (root == null) {
// return 0;
// }
// int leftMax = Math.max(maxPathSumCount(root.getLeftChild()), 0);
// int rightMax = Math.max(maxPathSumCount(root.getRightChild()), 0);
// maxSum = Math.max((root.getValue() + leftMax + rightMax) , maxSum);
// return root.getValue() + Math.max(leftMax, rightMax);
// }
// public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// if (root == null){
// return null;
// }
//
// Stack<TreeNode> result1 = new Stack<>();
// Stack<TreeNode> result2 = new Stack<>();
// getAllAncestor(root,p,result1);
// getAllAncestor(root,q,result2);
//
//
// while (result1.size() != result2.size()){
// if (result1.size() > result2.size()){
// result1.pop();
// }
// if (result1.size() < result2.size()){
// result2.pop();
// }
// }
//
//
// while (result1.size() > 0){
// TreeNode treeNode = result1.pop();
// if (treeNode == result2.pop()){
// return treeNode;
// }
// }
// return null;
// }
// Stack<TreeNode> result = new Stack<>();
// public static TreeNode getAllAncestor(TreeNode root, TreeNode node,Queue<TreeNode> result){
// if (root != null){
// if (root.getValue() == node.getValue()){
// result.offer(root);
// return null;
// }
// if ((root.getLeftChild()!= null && root.getLeftChild().getValue() == node.getValue() )
// || (root.getRightChild()!= null && root.getRightChild().getValue() == node.getValue())){
// result.offer(node);
// result.offer(root);
// return root;
// }
// TreeNode node1 = getAllAncestor(root.getLeftChild(),node,result);
// if (node1 != null && root.getLeftChild().getValue() == node1.getValue()){
// result.offer(root);
// return root;
// }
//
// TreeNode node2 =getAllAncestor(root.getRightChild(),node,result);
// if (node2 != null && root.getRightChild().getValue() == node2.getValue()){
// result.offer(root);
// return root;
// }
//
// }
//
// return null;
// }
public static void getAllAncestor(TreeNode root, TreeNode node,Stack<TreeNode> result){
TreeNode currentNode = root;
TreeNode preNode = null;
while (currentNode != null || !result.isEmpty()) {
//左子樹
while (currentNode != null) {
result.push(currentNode);
if (currentNode.getValue() == node.getValue()){
return;
}
currentNode = currentNode.getLeftChild();
}
TreeNode popNode = result.pop();
currentNode = popNode.getRightChild();
//當前節(jié)點右子樹不為空（1.還未遍歷右子樹；2.已經遍歷過右子樹了，通過preNode是否與當前右子樹根結點相同來判斷）
if (currentNode != null && preNode != popNode.getRightChild()) {
result.push(popNode);
} else {
//記錄打印的值
preNode = popNode;
currentNode = null;
}
}
}
private TreeNode ans;
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.getLeftChild(), p, q);
boolean rson = dfs(root.getRightChild(), p, q);
//兩種情況：1.p,q分別在該節(jié)點的左右子樹中；2.p,q其中一個節(jié)點本身，另一個節(jié)點在其子樹上
if ((lson && rson) || ((root.getValue() == p.getValue() || root.getValue() == q.getValue()) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.getValue() == p.getValue() || root.getValue() == q.getValue());
}
/**
* 獲取最早公共祖先
* @param root
* @param p
* @param q
* @return
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
public static void main(String[] args) {
//[3,5,1,6,2,0,8,null,null,7,4]
TreeNode nodea = new TreeNode(3);
TreeNode nodeb = new TreeNode(5);
TreeNode nodec = new TreeNode(1);
TreeNode noded = new TreeNode(6);
TreeNode nodee = new TreeNode(2);
TreeNode nodef = new TreeNode(0);
TreeNode nodeg = new TreeNode(8);
TreeNode nodeh = new TreeNode(7);
TreeNode nodei = new TreeNode(4);
//TreeNode node3 = new TreeNode(3);
nodea.setLeftChild(nodeb);
nodea.setRightChild(nodec);
nodeb.setLeftChild(noded);
nodeb.setRightChild(nodee);
nodec.setLeftChild(nodef);
nodec.setRightChild(nodeg);
nodee.setLeftChild(nodeh);
nodee.setRightChild(nodei);
TreeNode node5 = new TreeNode(1);
TreeNode node1 = new TreeNode(5);
// TreeNode result = lowestCommonAncestor(nodea,node1,node5);
// Stack<TreeNode> result1 = new Stack<>();
// getAllAncestor(nodea,node5,result1);
// System.out.println(result.getValue());
// int a = 1;
// int b = 1;
// if (a == 1){
// System.out.println("aaaaaaaa");
// }else if (b == 1){
// System.out.println("bbbbbbbb");
// }else {
// System.out.println("ccccccccc");
// }
// System.out.println(maxPathSum(nodea));
// node1.setRightChild(node2);
// node2.setLeftChild(node3);
// node2.setRightChild(node4);
// postorderTraversal(node1);
//[0,2,4,1,null,3,-1,5,1,null,6,null,8]
// BinaryTree tree = new BinaryTree(node0);
// System.out.println(tree.hight());
}
}
leetcode上有相應的題，可以做一下：
先序遍歷：在做這個題如果使用遞歸算法的話，需要注意要將存儲結果的list傳入到遞歸循環(huán)中，
中序遍歷：同上。
后序遍歷：同上。
最大深度:直接使用BinaryTree類中獲取樹高的方法，一個遞歸的是深度優(yōu)先遍歷，一個非遞歸是廣度優(yōu)先遍歷。
是否平衡二叉樹判斷:我在二叉樹中的代碼寫了一個自底向上的判斷方法（isBalanced），時間復雜度為n，還可以自頂向下遍歷，對每個節(jié)點的左右子樹的高度進行比較（主要利用計算樹高的方法），時間復雜度為n的二次方；
計算root節(jié)點最大路徑和:這個題我覺得難在理解上，對于當前節(jié)點（node）而言，最大路徑和只有四種情況：（最大貢獻值怎么理解：空節(jié)點的最大貢獻值等于 0；非空節(jié)點的最大貢獻值等于節(jié)點值加上左右節(jié)點中較大貢獻值的節(jié)點的貢獻值；對于葉節(jié)點而言，最大貢獻值等于節(jié)點值）有點繞，慢慢理解吧
1.node本身的value;
2.左右節(jié)點的最大貢獻值都大于0--node.value+left.value+right.value;
3.左節(jié)點最大貢獻值大于0，右節(jié)點小于0--node.value+left.value；
4.左節(jié)點最大貢獻值小于0，右節(jié)點大于0--node.value+left.value
二叉樹的最近公共祖先:這個題我自己寫了遞歸和非遞歸的代碼，思路是用?；蛘哧犃邪错樞騼Υ鎯蓚€節(jié)點的祖先節(jié)點（包含自己本身），然后將較長的隊列或者棧的出隊或者出棧到較小長度的隊列或者棧的長度，然后一起出隊或者出棧，相同的第一個相同的節(jié)點就是最近公共祖先，但是結果不盡人意，遞歸的方法比官方的遞歸方法多一毫秒，所以我還是注釋掉了自己的代碼，留下了官方的代碼：
private TreeNode ans;
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.getLeftChild(), p, q);
boolean rson = dfs(root.getRightChild(), p, q);
//兩種情況：1.p,q分別在該節(jié)點的左右子樹中；2.p,q其中一個節(jié)點本身，另一個節(jié)點在其子樹上
if ((lson && rson) || ((root.getValue() == p.getValue() || root.getValue() == q.getValue()) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.getValue() == p.getValue() || root.getValue() == q.getValue());
}
/**
* 獲取最早公共祖先
* @param root
* @param p
* @param q
* @return
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
二叉樹的層序遍歷:最大深度的時候已經寫過這個方法了，稍微修改一下就可以了。
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> tempNode = new LinkedList<>();
tempNode.offer(root);
while (!tempNode.isEmpty()){
int count = tempNode.size();
List<Integer> tempList = new ArrayList<>();
while (count > 0){
root = tempNode.poll();
tempList.add(root.val);
if (root.left != null){
tempNode.offer(root.left);
}
if (root.right != null){
tempNode.offer(root.right);
}
count--;
}
result.add(tempList);
}
return result;
}
二叉樹的層序遍歷 II：這個也是層序遍歷，不過是結果逆序輸出，我想到辦法是使用棧，最后遍歷一棧，把結果輸出出來，不過官方的方案更好一點，利用了鏈表頭插法的為常量復雜度的性質，比我的方法更快：
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
if (root == null){
return levelOrder;
}
Queue<TreeNode> tempNode = new LinkedList<>();
tempNode.offer(root);
while (!tempNode.isEmpty()){
int count = tempNode.size();
List<Integer> tempList = new ArrayList<>();
while (count > 0){
root = tempNode.poll();
tempList.add(root.val);
if (root.left != null){
tempNode.offer(root.left);
}
if (root.right != null){
tempNode.offer(root.right);
}
count--;
}
levelOrder.add(0,tempList);//頭插法
}
return levelOrder;
}
二叉樹的鋸齒形層序遍歷:依舊是層序遍歷，我吸取了上道題利用鏈表頭插的特性，而官方則是利用雙向隊列，我們都使用一個標識來判斷是順序還是逆序，每遍歷一層就反轉一下或者利用層數奇偶性
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> tempNode = new LinkedList<>();
tempNode.offer(root);
boolean isOrderLeft = false;
while (!tempNode.isEmpty()){
int count = tempNode.size();
List<Integer> tempList = new LinkedList<>();
while (count > 0){
root = tempNode.poll();
if(isOrderLeft){
tempList.add(0,root.val);
}else{
tempList.add(root.val);
}
if (root.left != null){
tempNode.offer(root.left);
}
if (root.right != null){
tempNode.offer(root.right);
}
count--;
}
isOrderLeft = !isOrderLeft;
result.add(tempList);
}
return result;
}
驗證二叉搜索樹：通過不斷縮小邊界來判斷，對于root節(jié)點，邊界為正負無窮，對于root的左子樹而言，邊界為負無窮到root.val，對于右子樹而言，邊界為root.val到正無窮。
/**
* 驗證是否是搜索二叉樹（不斷縮小邊界來判斷）
* @param root
* @return
*/
public static boolean isValidBST(TreeNode root) {
if (root == null){
return true;
}
return isValidBST(root,Integer.MAX_VALUE,Integer.MIN_VALUE);
}
public static boolean isValidBST(TreeNode root,int maxValue,int minValue) {
if (root == null) {
return true;
}
if (root.getValue() <= minValue || root.getValue() >= maxValue){
return false;
}
return isValidBST(root.getLeftChild(),maxValue,root.getValue())&&isValidBST(root.getRightChild(),root.getValue(),minValue);
}
/**
* 插入搜索二叉樹
* @param root
* @param val
* @return
*/
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null){
return new TreeNode(val);
}
if (val < root.getValue()){
root.setLeftChild(insertIntoBST(root.getLeftChild(),val));
}else{
root.setRightChild(insertIntoBST(root.getRightChild(),val));
}
return root;
}
