溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
數據結構與算法中二叉樹子結構的詳解
需求
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
樹的描述：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
解決思路
使用了棧將元素入棧，并不斷的彈出元素，彈出一個元素的時候，拼接成字符串，并用特殊符號進行區分，該方法主要是按照先序遍歷的方式將樹節點的數據信息拼接為字符串，這樣，兩個樹的節點拼接而成的串進行判斷是不是包含。
不過，有的資料上說可以通過遞歸的方式進行，但是我感覺以及實踐以后發現是錯誤的。后面會給出代碼，讀者自行嘗試。
public static boolean HasSubtree2(TreeNode root1, TreeNode root2) {
if (root2 == null)
return false;
String str = "";
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(null);
stack.push(root1);
TreeNode node = null;
while ((node = stack.pop()) != null) {
str += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
String str2 = "";
node = null;
stack.push(null);
stack.push(root2);
while ((node = stack.pop()) != null) {
str2 += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
if (str.contains(str2)) {
return true;
} else {
return false;
}
}
樹的構建
二叉樹而言，可以通過數組的方式進行存放，首節點放在數組0號位置處，其左節點在1號位置處，其右節點在2號位置處。由此該index的映射關系為：
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
構建思路，左節點和右節點分別構建，根節點的左節點就一直追溯其子節點，根節點的右節點一直追溯其子節點，由此，形成的是遞歸的結構。
代碼如下：
注：這里數組中通過-1作為區分，讀者可自行擴充。
public static TreeNode getTree(int[] node, int index) {
if (index >= node.length)
return null;
TreeNode n = null;
if (node[index] != -1) {
n = new TreeNode(node[index]);
n.left = getTree(node, index * 2 + 1);
n.right = getTree(node, index * 2 + 2);
}
return n;
}
完整代碼
包括了資料中提供的代碼，但是經過測試如下用例中是錯誤的，但是理論上說tree2應該是tree1的子結構才對。
import java.util.Stack;
public class HasSubtree {
public static void main(String[] args) {
TreeNode tree = getTree(new int[] { 8, 8, 7, 9, 2, -1, -1, -1, -1, 4, 7 }, 0);
TreeNode tree2 = getTree(new int[] { 2, 4, 7 }, 0);
boolean bool = HasSubtree(tree, tree2);
System.out.println(bool);
boolean bool2 = HasSubtree2(tree, tree2);
System.out.println(bool2);
}
public static boolean HasSubtree2(TreeNode root1, TreeNode root2) {
if (root2 == null)
return false;
String str = "";
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(null);
stack.push(root1);
TreeNode node = null;
while ((node = stack.pop()) != null) {
str += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
String str2 = "";
node = null;
stack.push(null);
stack.push(root2);
while ((node = stack.pop()) != null) {
str2 += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
if (str.contains(str2)) {
return true;
} else {
return false;
}
}
public static TreeNode getTree(int[] node, int index) {
if (index >= node.length)
return null;
TreeNode n = null;
if (node[index] != -1) {
n = new TreeNode(node[index]);
n.left = getTree(node, index * 2 + 1);
n.right = getTree(node, index * 2 + 2);
}
return n;
}
public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean result = false;
if (root1 != null && root2 != null) {
if (root1.val == root2.val) {
result = isSubTree(root1, root2);
}
if (!result) {
result = isSubTree(root1.left, root2);
}
if (!result) {
result = isSubTree(root1.right, root2);
}
}
return result;
}
private static boolean isSubTree(TreeNode root1, TreeNode root2) {
if (root1 == null)
return false;
if (root2 == null)
return true;
if (root1.val != root2.val)
return false;
return isSubTree(root1.left, root2.left)
&& isSubTree(root1.right, root2.right);
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
