劍指offer - 16.樹的子結構

樹的子結構

知識點：二叉樹

題目：

輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）

解析：

• 思路：

代碼：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
        public boolean HasSubtree(TreeNode root1, TreeNode root2) {
            //result作為最後的結果傳回
            boolean result = false;
            if (root1 != null && root2 != null) {
                if (root1.val == root2.val) {
                    //判斷root1是否包含root2
                    result = doesTree1HaveTree2(root1, root2);
                }
                //root的左子樹上是否符合
                if (!result) {
                    result = HasSubtree(root1.left, root2);
                }
                //root的右子樹上是否符合
                if (!result) {
                    result = HasSubtree(root1.right, root2);
                }
            }
            return result;
        }

        public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
            //如果node2周遊完都能對應上，傳回true
            //這個判斷需要放在下面一個判斷的前面
            if (node2 == null) {
                return true;
            }
            if (node1 == null) {
                return false;
            }
            //如果node1.val!=node2.val, 傳回false
            if (node1.val != node2.val)
                return false;
            //如果根結點對應上，則分别在子結點上去比對
            return doesTree1HaveTree2(node1.right, node2.right) && doesTree1HaveTree2(node1.left, node2.left);
        }
    }