溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹子結(jié)構(gòu)的詳解
需求
輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
樹的描述：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
解決思路
使用了棧將元素入棧，并不斷的彈出元素，彈出一個(gè)元素的時(shí)候，拼接成字符串，并用特殊符號進(jìn)行區(qū)分，該方法主要是按照先序遍歷的方式將樹節(jié)點(diǎn)的數(shù)據(jù)信息拼接為字符串，這樣，兩個(gè)樹的節(jié)點(diǎn)拼接而成的串進(jìn)行判斷是不是包含。
不過，有的資料上說可以通過遞歸的方式進(jìn)行，但是我感覺以及實(shí)踐以后發(fā)現(xiàn)是錯(cuò)誤的。后面會(huì)給出代碼，讀者自行嘗試。
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;
}
}
樹的構(gòu)建
二叉樹而言，可以通過數(shù)組的方式進(jìn)行存放，首節(jié)點(diǎn)放在數(shù)組0號位置處，其左節(jié)點(diǎn)在1號位置處，其右節(jié)點(diǎn)在2號位置處。由此該index的映射關(guān)系為：
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
構(gòu)建思路，左節(jié)點(diǎn)和右節(jié)點(diǎn)分別構(gòu)建，根節(jié)點(diǎn)的左節(jié)點(diǎn)就一直追溯其子節(jié)點(diǎn)，根節(jié)點(diǎn)的右節(jié)點(diǎn)一直追溯其子節(jié)點(diǎn)，由此，形成的是遞歸的結(jié)構(gòu)。
代碼如下：
注：這里數(shù)組中通過-1作為區(qū)分，讀者可自行擴(kuò)充。
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;
}
完整代碼
包括了資料中提供的代碼，但是經(jīng)過測試如下用例中是錯(cuò)誤的，但是理論上說tree2應(yīng)該是tree1的子結(jié)構(gòu)才對。
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;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼