2019年9月15日
繼續彌補《資料結構與算法》的不足，今天抽中了“樹”。決定先把基礎題做一遍，打好基礎。
目錄
題目：
解決方法1：
解決思路：
性能結果：
解決方法2：
思路：深度優先周遊
解決方法3：
疊代
複雜度分析
遞歸
複雜度分析
題目：
二叉樹基礎概念：
樹是一種抽象資料類型（ADT）或是實作這種抽象資料類型的資料結構，用來模拟具有樹狀結構性質的資料集合。它是由 n(n>0)n(n>0) 個有限節點組成一個具有層次關系的集合。
把它叫做「樹」是因為它看起來像一棵倒挂的樹，也就是說它是根朝上，而葉朝下的。
它具有以下的特點：
- 每個節點都隻有有限個子節點或無子節點；
- 沒有父節點的節點稱為根節點；
- 每一個非根節點有且隻有一個父節點；
- 除了根節點外，每個子節點可以分為多個不相交的子樹；
- 樹裡面沒有環路。
解決方法1：
package leetCode.tree;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* REMARK 相同的樹
*
* @author: mmb
* @date: 19-9-15
*/
public class TwoSameTreeSolution {
public static void main(String[] args){
TreeNode p = getATree();
// TreeNode q = getATree();
TreeNode q = getATreeV2();
System.out.println("result = " + isSameTree(p, q));
}
/**
* 比較兩棵樹是否相同
*/
public static boolean isSameTree(TreeNode p, TreeNode q){
List<Integer> tree1AllNodes = getAllNodes(p);
List<Integer> tree2AllNodes = getAllNodes(q);
System.out.println("tree1AllNodes = " + tree1AllNodes);
System.out.println("tree2AllNodes = " + tree2AllNodes);
return compareTwoTree(tree1AllNodes, tree2AllNodes);
}
/**
* 比較兩棵樹的結點清單
*/
private static boolean compareTwoTree(List<Integer> tree1AllNodes, List<Integer> tree2AllNodes) {
// 兩棵樹的節點要一樣
if (tree1AllNodes.size() == tree2AllNodes.size()){
int countTime = 0;
int tree1NotNullCount = 0;
int tree2NotNullCount = 0;
Iterator<Integer> iterator1 = tree1AllNodes.iterator();
Iterator<Integer> iterator2 = tree2AllNodes.iterator();
// 逐個周遊兩棵樹的節點
while (iterator1.hasNext()){
Integer tree1Node = iterator1.next();
Integer tree2Node = iterator2.next();
// 兩棵樹的節點都不為空
if (tree1Node != null && tree2Node != null){
if (tree1Node.equals(tree2Node)){
countTime++;
continue;
} else {
break;
}
}
// 兩棵樹的節點都為空
else if (tree1Node == null && tree2Node == null) {
continue;
}
// 其中一棵樹節點為空
else {
break;
}
}
// tree1的非空節點
for (Integer node : tree1AllNodes){
if (node != null){
tree1NotNullCount++;
}
}
// tree2的非空節點
for (Integer node : tree2AllNodes){
if (node != null){
tree2NotNullCount++;
}
}
// tree1和tree2和節點比較相同次數一樣
if (tree1NotNullCount == countTime && tree2NotNullCount == countTime){
return true;
}
}
return false;
}
/**
* 擷取所有節點資料
*/
private static List<Integer> getAllNodes(TreeNode node){
// 前序周遊,遞歸擷取所有節點資訊
ArrayList<Integer> treeNodes = new ArrayList<>();
if(node != null){
treeNodes.add(node.val);
if (node.left != null){
List<Integer> allLeftNodes = getAllNodes(node.left);
treeNodes.addAll(allLeftNodes);
} else if (node.right != null){
treeNodes.add(null);
}
if (node.right != null){
List<Integer> allRightNodes = getAllNodes(node.right);
treeNodes.addAll(allRightNodes);
}
}
return treeNodes;
}
/**
* 建立一棵樹
*/
public static TreeNode getATree(){
TreeNode headNode = new TreeNode(1);
TreeNode leftNode = new TreeNode(2);
TreeNode rightNode = new TreeNode(3);
headNode.setLeft(leftNode);
headNode.setRight(rightNode);
return headNode;
}
public static TreeNode getATreeV2(){
TreeNode headNode = new TreeNode(1);
TreeNode leftNode = new TreeNode(2);
TreeNode rightNode = new TreeNode(3);
headNode.setLeft(leftNode);
headNode.setRight(rightNode);
return headNode;
}
} 解決思路：
- 對于給定的兩棵樹，我是首先想到的是遞歸周遊（這裡使用前序周遊：根節點-左子樹-右子樹），也就是說将樹的所有節點全部拿出到list裡面；第二步，就是逐個對比list的節點是否相同；
- 這種方法比較笨，我這種初學者往往會往死胡同裡面走；這時候算法展現出優越性了。。。
性能結果：
解決方法2：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
作者：guanpengchn
思路：深度優先周遊
終止條件與傳回值：
- 當兩棵樹的目前節點都為 null 時傳回 true
- 當其中一個為 null 另一個不為 null 時傳回 false
- 當兩個都不為空但是值不相等時，傳回 false
執行過程：當滿足終止條件時進行傳回，不滿足時分别判斷左子樹和右子樹是否相同，其中要注意代碼中的短路效應
時間複雜度：O(n)，n 為樹的節點個數
解決方法3：
疊代
- 最簡單的政策是使用遞歸。檢查p和q節點是否不是空，它們的值是否相等。如果所有檢查都正常，則遞歸地為子節點執行相同操作。
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// p 和 q 均為 null時
if (p == null && q == null) return true;
// p 或 q 有一個為null時
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return isSameTree(p.right, q.right) &&
isSameTree(p.left, q.left);
}
}
作者：gaohanghang
複雜度分析
時間複雜度：O(N)，其中N是樹中的節點數，因為每個節點隻通路一次。
空間複雜度：O(log(N))：
在最佳情況下即completely balanced tree空間複雜度是O(log(N))，
在最壞情況下 completely unbalanced tree空間複雜度是O(N)，和遞歸次數保持一緻。
遞歸
- 思路：從根開始，在每次疊代時将目前節點彈出deque。
- 然後執行與方法1中相同的檢查：p 和 q 不為空，p.val 和 q.val 相等，如果檢查正常，則push子節點。
class Solution {
public boolean check(TreeNode p, TreeNode q) {
// p and q are null
if (p == null && q == null) return true;
// one of p and q is null
if (q == null || p == null) return false;
if (p.val != q.val) return false;
return true;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (!check(p, q)) return false;
// init deques
ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();
deqP.addLast(p);
deqQ.addLast(q);
while (!deqP.isEmpty()) {
p = deqP.removeFirst();
q = deqQ.removeFirst();
if (!check(p, q)) return false;
if (p != null) {
// in Java nulls are not allowed in Deque
if (!check(p.left, q.left)) return false;
if (p.left != null) {
deqP.addLast(p.left);
deqQ.addLast(q.left);
}
if (!check(p.right, q.right)) return false;
if (p.right != null) {
deqP.addLast(p.right);
deqQ.addLast(q.right);
}
}
}
return true;
}
}
作者：gaohanghang