数据布局与算法中二叉树子布局的详解

数据布局与算法中二叉树子布局的详解

需求

输入两棵二叉树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,4,7 },0);
    TreeNode tree2 = getTree(new int[] { 2,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,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;

  }

}

感激阅读，但愿能辅佐到各人，感谢各人对本站的支持！

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!