數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹子結(jié)構(gòu)的詳解
需求
輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）
樹的描述：
class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}解決思路
使用了棧將元素入棧，并不斷的彈出元素，彈出一個元素的時候，拼接成字符串，并用特殊符號進行區(qū)分，該方法主要是按照先序遍歷的方式將樹節(jié)點的數(shù)據(jù)信息拼接為字符串，這樣，兩個樹的節(jié)點拼接而成的串進行判斷是不是包含。
不過，有的資料上說可以通過遞歸的方式進行，但是我感覺以及實踐以后發(fā)現(xiàn)是錯誤的。后面會給出代碼，讀者自行嘗試。
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ù)組的方式進行存放，首節(jié)點放在數(shù)組0號位置處，其左節(jié)點在1號位置處，其右節(jié)點在2號位置處。由此該index的映射關(guān)系為：
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
構(gòu)建思路，左節(jié)點和右節(jié)點分別構(gòu)建，根節(jié)點的左節(jié)點就一直追溯其子節(jié)點，根節(jié)點的右節(jié)點一直追溯其子節(jié)點，由此，形成的是遞歸的結(jié)構(gòu)。
代碼如下：
注：這里數(shù)組中通過-1作為區(qū)分，讀者可自行擴充。
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)過測試如下用例中是錯誤的，但是理論上說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; }}感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
