前言：題圖無關，現在開始來學習學習樹相關的知識
前序文章：
- 資料結構與算法(1)——數組與連結清單（https://www.jianshu.com/p/7b93b3570875）
- 資料結構與算法(2)——棧和隊列(https://www.jianshu.com/p/5087c751cb42)
樹
什麼是樹
樹是一種類似于連結清單的資料結構，不過連結清單的結點是以線性方式簡單地指向其後繼結點，而樹的一個結點可以指向許多個結點；數是一種典型的非線性結構；樹結構是以表達具有層次特性的圖結構的一種方法；
相關術語
- 根節點：根節點是一個沒有雙親結點的結點，一棵樹中最多有一個根節點（如上圖的結點A就是根節點）；
- 邊：邊表示從雙親結點到孩子結點的連結（如上圖中所有的連結）；
- 葉子結點：沒有孩子結點的結點叫作葉子結點（如E、J、K、H和I）；
- 兄弟結點：擁有相同雙親結點的所有孩子結點叫作兄弟結點（B、C、D是A的兄弟結點，E、F是B的兄弟結點）；
- 祖先結點：如果存在一條從根節點到結點q的路徑，其結點p出現在這條路徑上，那麼就可以吧結點p叫作結點q的祖先結點，結點q也叫做p的子孫結點（例如，A、C和G是K的祖先結點）；
- 結點的大小：結點的大小是指子孫的個數，包括其自身。（子樹C的大小為3）；
- 樹的層：位于相同深度的所有結點的集合叫作樹的層（B、C和D具有相同的層，上圖的結構有0/1/2/3四個層）；
- 結點的深度：是指從根節點到該節點的路徑長度（G點的深度為2，A—C—G）；
- 結點的高度：是指從該節點到最深節點的路徑長度，樹的高度是指從根節點到書中最深結點的路徑長度，隻含有根節點的樹的高度為0。（B的高度為2，B—F—J）；
- 樹的高度：是樹中所有結點高度的最大值，樹的深度是樹中所有結點深度的最大值，對于同一棵樹，其深度和高度是相同的，但是對于各個結點，其深度和高度不一定相同；
二叉樹
如果一棵樹中的每個結點有0，1或者2個孩子結點，那麼這棵樹就稱為二叉樹；空樹也是一顆有效的二叉樹，一顆二叉樹可以看做是由根節點和兩棵不相交的子樹（分别稱為左子樹和右子樹）組成，如下圖所示。
二叉樹的類型
嚴格二叉樹：二叉樹中的每個節點要麼有兩個孩子結點，要麼沒有孩子結點
滿二叉樹：二叉樹中的每個結點恰好有兩個孩子結點且所有葉子結點都在同一層
完全二叉樹：在定義完全二叉樹之前，假定二叉樹的高度為h；對于完全二叉樹，如果将所有結點從根節點開始從左至右，從上至下，依次編号（假定根節點的編号為1），那麼僵得到從1~n（n為結點總數）的完整序列，在周遊過程中對于空指針也賦予編号，如果所有伽椰子結點的深度為h或h-1，且在結點編号序列中沒有漏掉任何數字，那麼這樣的二叉樹叫作完全二叉樹。
二叉樹的應用
- 編譯器中的表達式樹；
- 用于資料壓縮算法中的赫夫曼編碼樹；
- 支援在集合中查找、插入和删除，其平均時間複雜度為O(lognn)的二叉搜尋樹（BST）；
- 優先隊列（PQ），它支援以對數時間（最壞情況下）對集合中的最小（或最大）資料元素進行搜尋和删除；
二叉樹的周遊
通路樹中所有結點的過程叫作樹的周遊，在周遊過程中，每個結點隻能被處理一次，盡管其有可能被通路多次；根據結點處理順序的不同，。可以定義不同的周遊方法，周遊分類可以根據目前節點被處理的順序來劃分：
前序周遊
在前序周遊中，每個結點都是在它的子樹周遊之前進行處理，這是最容易了解的便利方法，然而，盡管每個結點在其子樹之前進行了處理，但在向下移動的過程仍然需要保留一些資訊，以上圖為例，首先通路結點1，随後周遊其左子樹，最後周遊其右子樹，是以當左子樹周遊完後，必須要傳回到其右子樹來繼續周遊；為了能夠在左子樹周遊完成後移動到右子樹，必須保留根節點的資訊，能夠實作該資訊存儲的抽象資料類型顯而易見是棧，由于它是LIFO的結構，是以它可以以逆序來彙過去該資訊并傳回到右子樹；
前序周遊可以如下定義：
- 通路根節點；
- 按前序周遊方式周遊左子樹；
- 按前序周遊方式周遊右子樹；
利用前序周遊方法上圖所示的樹的輸出序列為：1 2 4 5 3 6 7
void preOrder(BinaryTreeNode root) {
if (null != root) {
System.out.println(root.getData());
preOrder(root.getLeft());
preOrder(root.getRight());
}
}
中序周遊
在中序周遊中，根節點的通路在兩棵子樹的周遊中間完成，中序周遊如下定義：
- 按中序周遊方式周遊左子樹；
- 按中序周遊方式周遊右子樹；
基于中序周遊，上圖所示樹的中序周遊輸出順序為：4 2 5 1 6 3 7
void inOrder(BinaryTreeNode root) {
if (null != root) {
inOrder(root.getLeft());
System.out.println(root.getData());
inOrder(root.getRight());
}
}
後序周遊
在後續周遊中，根節點的通路是在其兩棵子樹都周遊完成後進行的，後續周遊如下定義：
- 按後序周遊左子樹；
- 按後序周遊右子樹；
對上圖所示的二叉樹，後續周遊産生的輸出序列為：4 5 2 6 7 3 1
void postOrder(BinaryTreeNode root) {
if (null != root) {
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.println(root.getData());
}
}
層次周遊
層次周遊的定義如下：
- 在通路第l層時，将l+1層的節點按順序儲存在隊列中；
- 進入下一層并通路該層的所有結點；
- 重複上述操作直至所有層都通路完；
對于上圖所示的二叉樹，層次周遊産生的輸出序列為：1 2 3 4 5 6 7
void levelOrder(BinaryTreeNode root) {
BinaryTreeNode temp;
LoopQueue Q = new LoopQueue();
if (null == root) {
return;
}
Q.enqueue(root);
while (!Q.isEmpty()) {
temp = Q.dequeue();
// 處理目前節點
System.out.println(temp.getData());
if (temp.getLeft()) {
Q.enqueue(temp.getLeft());
}
if (temp.getRight()) {
Q.enqueue(temp.getRight());
}
}
// 删除隊列中的所有資料
Q.deletequeue();
}
二叉搜尋樹
在二叉搜尋樹中，所有左子樹結點的元素小于根節點的資料，所有右子樹結點的元素大于根節點資料，注意，樹中的每個結點都應滿足這個性質；
實作自己的二叉搜尋樹
其中包含了常用的一些方法，包括幾種周遊方法還有查詢、删除等，僅供參考：
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 向二分搜尋樹中添加新的元素e
public void add(E e){
root = add(root, e);
}
// 向以node為根的二分搜尋樹中插入元素e，遞歸算法
// 傳回插入新節點後二分搜尋樹的根
private Node add(Node node, E e){
if(node == null){
size ++;
return new Node(e);
}
if(e.compareTo(node.e) < 0)
node.left = add(node.left, e);
else if(e.compareTo(node.e) > 0)
node.right = add(node.right, e);
return node;
}
// 看二分搜尋樹中是否包含元素e
public boolean contains(E e){
return contains(root, e);
}
// 看以node為根的二分搜尋樹中是否包含元素e, 遞歸算法
private boolean contains(Node node, E e){
if(node == null)
return false;
if(e.compareTo(node.e) == 0)
return true;
else if(e.compareTo(node.e) < 0)
return contains(node.left, e);
else // e.compareTo(node.e) > 0
return contains(node.right, e);
}
// 二分搜尋樹的前序周遊
public void preOrder(){
preOrder(root);
}
// 前序周遊以node為根的二分搜尋樹, 遞歸算法
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
// 二分搜尋樹的非遞歸前序周遊
public void preOrderNR(){
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
// 二分搜尋樹的中序周遊
public void inOrder(){
inOrder(root);
}
// 中序周遊以node為根的二分搜尋樹, 遞歸算法
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
// 二分搜尋樹的後序周遊
public void postOrder(){
postOrder(root);
}
// 後序周遊以node為根的二分搜尋樹, 遞歸算法
private void postOrder(Node node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
// 二分搜尋樹的層序周遊
public void levelOrder(){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
}
// 尋找二分搜尋樹的最小元素
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return minimum(root).e;
}
// 傳回以node為根的二分搜尋樹的最小值所在的節點
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 尋找二分搜尋樹的最大元素
public E maximum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
return maximum(root).e;
}
// 傳回以node為根的二分搜尋樹的最大值所在的節點
private Node maximum(Node node){
if(node.right == null)
return node;
return maximum(node.right);
}
// 從二分搜尋樹中删除最小值所在節點, 傳回最小值
public E removeMin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
// 删除掉以node為根的二分搜尋樹中的最小節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 從二分搜尋樹中删除最大值所在節點
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
// 删除掉以node為根的二分搜尋樹中的最大節點
// 傳回删除節點後新的二分搜尋樹的根
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// 從二分搜尋樹中删除元素為e的節點
public void remove(E e){
root = remove(root, e);
}
// 删除掉以node為根的二分搜尋樹中值為e的節點, 遞歸算法
// 傳回删除節點後新的二分搜尋樹的根
private Node remove(Node node, E e){
if( node == null )
return null;
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left , e);
return node;
}
else if(e.compareTo(node.e) > 0 ){
node.right = remove(node.right, e);
return node;
}
else{ // e.compareTo(node.e) == 0
// 待删除節點左子樹為空的情況
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待删除節點右子樹為空的情況
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待删除節點左右子樹均不為空的情況
// 找到比待删除節點大的最小節點, 即待删除節點右子樹的最小節點
// 用這個節點頂替待删除節點的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
// 生成以node為根節點，深度為depth的描述二叉樹的字元串
private void generateBSTString(Node node, int depth, StringBuilder res){
if(node == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e +"\n");
generateBSTString(node.left, depth + 1, res);
generateBSTString(node.right, depth + 1, res);
}
private String generateDepthString(int depth){
StringBuilder res = new StringBuilder();
for(int i = 0 ; i < depth ; i ++)
res.append("--");
return res.toString();
}
}
LeetCode相關題目整理
94.二叉樹的中序周遊
我的答案：（1ms）
public List<Integer> inorderTraversal(TreeNode root) {
List result = new ArrayList();
if (null != root) {
result.addAll(inorderTraversal(root.left));
result.add(root.val);
result.addAll(inorderTraversal(root.right));
}
return result;
}
參考答案：（0ms）
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root,List<Integer> list) {
if(root!=null){
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}
98. 驗證二叉搜尋樹
我的答案：（53ms）
private static int INT_MIN = Integer.MIN_VALUE;
private static int INT_MAX = Integer.MAX_VALUE;
public boolean isValidBST(TreeNode root) {
// 如果節點為空則滿足二叉搜尋樹條件
if (null == root) {
return true;
}
// 如果左孩子結點大于了根節點則傳回false
if (null != root.left && findMax(root.left) > root.val) {
return false;
}
// 如果右孩子結點小于了根節點則傳回false
if (null != root.right && findMin(root.right) < root.val) {
return false;
}
// 遞歸判斷左子樹和右子樹，若其中有一顆不是BST樹，則傳回false
if (!isValidBST(root.left) || !isValidBST(root.right)) {
return false;
}
// 通過所有判斷則是一顆BST樹
return true;
}
/**
* 找到一顆非空樹中的最大值
*
* @param root
* @return
*/
private int findMax(TreeNode root) {
int maxVal = INT_MIN;
int leftMaxVal = INT_MIN;
int rightMaxVal = INT_MIN;
if (null != root) {
// 最大值預設等于目前節點值
maxVal = root.val;
leftMaxVal = findMax(root.left);
rightMaxVal = findMax(root.right);
// maxVal等于目前maxVal與leftMaxVal中較大的一個
maxVal = maxVal > leftMaxVal ? maxVal : leftMaxVal;
// maxVal等于目前maxVal與rightMaxVal中較大的一個
maxVal = maxVal > rightMaxVal ? maxVal : rightMaxVal;
}
return maxVal;
}
/**
* 找到一顆非空樹的最小值
*
* @param root
* @return
*/
private int findMin(TreeNode root) {
int minVal = INT_MAX;
int leftMinVal = INT_MAX;
int rightMinVal = INT_MAX;
if (null != root) {
// 最小值預設為目前節點值
minVal = root.val;
leftMinVal = findMin(root.left);
rightMinVal = findMin(root.right);
// minVal等于目前minVal與leftMinVal中較小的一個
minVal = minVal < leftMinVal ? minVal : leftMinVal;
// minVal等于目前minVal與rightMinVal中較小的一個
minVal = minVal < rightMinVal ? minVal : rightMinVal;
}
return minVal;
}
自己寫的時候送出錯了很多次..沒有掌握到二分搜尋樹的精髓..
參考答案：（2ms）
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
if (root == null) return true;
if (root.val <= low || root.val >= high) return false;
return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}
這答案寫得我服了..真服..
101. 對稱二叉樹（劍指Offer面試題28）
參考答案：（12ms）
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
public boolean isSymmetric(TreeNode root1, TreeNode root2) {
if (null == root1 && null == root2) {
return true;
}
if (null == root1 || null == root2) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}
自己做的思路是使用中序周遊來判斷（轉成數組之後是對稱的），但是出了很多問題，就是需要考慮null值，中序周遊中并不能很好地把一棵樹儲存為一個完整二叉樹的樣子..是以看了下參考答案..寫得服..
104. 二叉樹的最大深度（劍指Offer面試題55）
我的答案：（3ms）
public int maxDepth(TreeNode root) {
int leftHeight, rightHeight;
if (null == root) {
return 0;
} else { // 計算每個子樹的高度
leftHeight = maxDepth(root.left);
rightHeight = maxDepth(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
}
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
}
105. 從前序與中序周遊序列構造二叉樹（劍指Offer面試題7）
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int ps, int is, int ie) {
int val = preorder[ps];
TreeNode node = new TreeNode(val);
int iRoot = ie;
while (iRoot > is) {
if (val == inorder[iRoot]) {
break;
}
iRoot--;
}
if (iRoot > is) {
node.left = buildTree(preorder, inorder, ps + 1, is, iRoot - 1);
}
if (iRoot < ie) {
node.right = buildTree(preorder, inorder, ps + 1 + (iRoot - is), iRoot + 1, ie);
}
return node;
}
思路是這樣的：在二叉樹的前序周遊序列中，第一個數字總是樹的根節點的值，但在中序周遊序列中，根節點的值儲存在序列的中間，左子樹的節點的值位于根節點的值的左邊，而右子樹則相反，然後既然找到了左右子樹我們又可以使用同樣的方法在前序和中序中分别建構左右子樹，這樣我們就能夠使用遞歸的方法完成；（上面算法中的ps、is、ie分别表示前序的開始位置，中序的開始位置和中序的結束位置；）
113. 路徑總和 II（劍指Offer面試題34）
參考答案：（3ms）
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<Integer> nodeList = new ArrayList<Integer>();
List<List<Integer>> sumList = new ArrayList<List<Integer>>();
if (root == null) {
return sumList;
}
pathSum2(root, sum, sumList, nodeList);
return sumList;
}
public void pathSum2(TreeNode root, int target,
List<List<Integer>> sumList, List<Integer> nodeList) {
if (root.left == null && root.right == null) {
nodeList.add(root.val);
int sum = 0;
for (Integer integer : nodeList) {
sum += integer;
}
if (sum == target) {
sumList.add(new ArrayList<Integer>(nodeList));
}
return;
}
nodeList.add(root.val);
if (root.left != null) {
pathSum2(root.left, target, sumList, nodeList);
nodeList.remove(nodeList.size() - 1);
}
if (root.right != null) {
pathSum2(root.right, target, sumList, nodeList);
nodeList.remove(nodeList.size() - 1);
}
}
230. 二叉搜尋樹中第K小的元素（類似劍指Offer面試題54）
我的答案：（23ms）
public int kthSmallest(TreeNode root, int k) {
// 正确性判斷
if (null == root || k < 1) {
return -1;
}
List<Integer> result = preOrder(root);
// 從小到大排序
Collections.sort(result);
return result.get(k - 1);
}
/**
* 周遊整棵樹并傳回一個List
*
* @param root
* @return
*/
private List<Integer> preOrder(TreeNode root) {
List result = new ArrayList();
if (null != root) {
result.add(root.val);
result.addAll(preOrder(root.left));
result.addAll(preOrder(root.right));
}
return result;
}
賊蠢，完全沒有用到二叉搜尋樹的特性
參考答案：（1ms）
public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if (k <= count) {
return kthSmallest(root.left, k);
} else if (k > count + 1) {
return kthSmallest(root.right, k - 1 - count);
}
return root.val;
}
public int countNodes(TreeNode n) {
if (n == null) return 0;
return 1 + countNodes(n.left) + countNodes(n.right);
}
449. 序列化二叉搜尋樹（類似劍指Offer面試題37）
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuffer sb = new StringBuffer();
preOrder(root,sb);
return sb.toString();
}
private static void preOrder(TreeNode root, StringBuffer sb){
if(root==null)
return;
sb.append(root.val).append('#');
preOrder(root.left,sb);
preOrder(root.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data==null)
return null;
int val =0;
TreeNode root = null;
for(int i=0;i<data.length();i++){
if(data.charAt(i)!='#'){
val = val*10+(data.charAt(i)-'0');
}else{
root = insert(root,val);
val=0;
}
}
return root;
}
private static TreeNode insert(TreeNode root,int val){
if(root==null)
return new TreeNode(val);
if(root.val<val)
root.right = insert(root.right,val);
else
root.left = insert(root.left,val);
return root;
}
572. 另一個樹的子樹（類似劍指Offer面試題26）
參考答案：（15ms）
public boolean isSubtree(TreeNode s, TreeNode t) {
// Write your code here
if (s == null) {
return t == null;
}
if (s.val == t.val && isSametree(s, t)) {
return true;
}
return isSubtree(s.left, t) | isSubtree(s.right, t);
}
private boolean isSametree(TreeNode s, TreeNode t) {
if (s == null) {
return t == null;
}
if (t == null) {
return false;
}
if (s.val != t.val) {
return false;
}
return isSametree(s.left, t.left) & isSametree(s.right, t.right);
}
我的第一個反應還是去把兩棵樹的前序周遊的數組弄出來然後判斷是否為子集，但是樹這樣的天然遞歸結構這樣寫很自然...
簡單總結
還是隻是簡單複習了一下樹的相關知識吧，通過刷LeetCode題目還有參照着劍指Offer對二叉樹、二叉搜尋樹僅僅這兩種結構有了一個較深的認識，因為後續還會繼續用到，是以這裡簡單複習一下也無所謂，不過看着題目倒是感覺這樣的結構很容易考面試題啊，因為這些結構既重要考點又多...
歡迎轉載，轉載請注明出處！
簡書ID：@我沒有三顆心髒
github：wmyskxz
歡迎關注公衆微信号：wmyskxz_javaweb
分享自己的Java Web學習之路以及各種Java學習資料
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)