【剑指offer-Java版】18树的子结构

素颜马尾好姑娘i 2022-08-21 08:58 138阅读 0赞

树的子结构：输入两棵二叉树A B，判断B是不是A的子结构

就是一个递归加上一个树的先序遍历

public class _Q18 {
    
        public boolean HasSubTree(BinaryTreeNode tree1, BinaryTreeNode tree2) {
            if (tree1 == null) return false;
            if (tree2 == null) return true; // 对于一棵空的树，默认是任何非空树都是包含空树的
    
            boolean result = false;
            if (tree1.value == tree2.value) {
                result = DoesTree1HasTree2(tree1, tree2);
            }
            if (!result) { // 如果没找到就在左子树中寻找
                result = HasSubTree(tree1.leftChild, tree2);
            }
            if (!result) { // 如果仍然没有找到就在右子树中寻找
                result = HasSubTree(tree1.rightChild, tree2);
            }
    
            return result;
        }
    
        private boolean DoesTree1HasTree2(BinaryTreeNode tree1, BinaryTreeNode tree2){
            if(tree2 == null) return true;
            if(tree1 == null) return false;
    
            boolean result = false;
            if(tree1.value != tree2.value){
                return false;
            }else{
                result = DoesTree1HasTree2(tree1.leftChild, tree2.leftChild) 
                        && DoesTree1HasTree2(tree1.rightChild, tree2.rightChild);
            }
    
            return result;
        }
        }

测试代码：

public class _Q18Test extends TestCase {
    
        _Q18 subTree = new _Q18();
    
        public void test(){
            BinaryTreeNode node0 = new BinaryTreeNode();
            BinaryTreeNode node1 = new BinaryTreeNode();
            BinaryTreeNode node2 = new BinaryTreeNode();
            BinaryTreeNode node3 = new BinaryTreeNode();
            BinaryTreeNode node4 = new BinaryTreeNode();
            BinaryTreeNode node5 = new BinaryTreeNode();
            BinaryTreeNode node6 = new BinaryTreeNode();
    
            BinaryTreeNode node7 = new BinaryTreeNode();
            BinaryTreeNode node8 = new BinaryTreeNode();
            BinaryTreeNode node9 = new BinaryTreeNode();
    
            node0.value = 8;
            node1.value = 8;
            node2.value = 7;
            node3.value = 9;
            node4.value = 2;
            node5.value = 4;
            node6.value = 7;
    
            node7.value = 8;
            node8.value = 9;
            node9.value = 2; // 改动以修改成一棵不在tree1中的子树
    
            node0.leftChild = node1;
            node0.rightChild = node2;
            node1.leftChild = node3;
            node1.rightChild = node4;
            node4.leftChild = node5;
            node4.rightChild = node6;
    
            node2.leftChild = null; node2.rightChild = null;
            node3.leftChild = null; node3.rightChild = null;
            node5.leftChild = null; node5.rightChild = null;
            node6.leftChild = null; node6.rightChild = null;
    
            node7.leftChild = node8;
            node7.rightChild = node9;
    
            node8.leftChild = null; node8.rightChild = null;
            node9.leftChild = null; node9.rightChild = null;
    
            System.out.println(subTree.HasSubTree(null, node7));
        }
        }