2018-12-02 18:58:21 +0000   |     algorithm leetcode tree binary tree   |   Viewed times   |    

题目

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2
Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0
Given tree t:
   4
  / \
 1   2

先找到相同的根节点,然后比较两棵子树

例子1中的st如下

Given tree s:

     3
    / \
   4   5
  / \
 1   2
Given tree t:
   4
  / \
 1   2

先在s中找到4节点,然后比较以4节点为根节点的子树和t树。

代码,用一个List储存所有节点的引用

class Solution {

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;
        int val = t.val;
        List<TreeNode> nodes = getNodes(s);
        for (TreeNode node : nodes) {
            if (node.val == val && compare(node, t)) return true;
        }
        return false;
    }

    private List<TreeNode> getNodes(TreeNode root) {
        List<TreeNode> list = new LinkedList<>();
        List<TreeNode> level = new LinkedList<>();
        level.add(root);
        while (!level.isEmpty()) {
            int size = level.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = level.remove(0);
                if (node != null) {
                    list.add(node);
                    level.add(node.left);
                    level.add(node.right);
                }
            }
        }
        return list;
    }

    private boolean compare(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        if (!compare(s.left, t.left) || !compare(s.right, t.right)) return false;
        return true;
    }

}

用迭代器遍历一棵二叉树

class Solution {

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;
        int val = t.val;
        Iterator ite = iterator(s);
        while (ite.hasNext()) {
            TreeNode node = ite.next();
            if (node.val == val && compare(node, t)) return true;
        }
        return false;
    }

    private Iterator iterator(TreeNode root) {
        return new Iterator(root);
    }

    private static class Iterator {
        private List<TreeNode> level;
        public Iterator (TreeNode root) {
            level = new LinkedList<TreeNode>();
            level.add(root);
        }
        public boolean hasNext() {
            while (!level.isEmpty() && level.get(0) == null) level.remove(0); // trim leading null nodes
            return !level.isEmpty();
        }
        public TreeNode next() {
            while (!level.isEmpty() && level.get(0) == null) level.remove(0); // trim leading null nodes
            if (!level.isEmpty()) {
                TreeNode next = level.remove(0);
                level.add(next.left);
                level.add(next.right);
                return next;
            }
            return null;
        }
    }

    private List<TreeNode> getNodes(TreeNode root) {
        List<TreeNode> list = new LinkedList<>();
        List<TreeNode> level = new LinkedList<>();
        level.add(root);
        while (!level.isEmpty()) {
            int size = level.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = level.remove(0);
                if (node != null) {
                    list.add(node);
                    level.add(node.left);
                    level.add(node.right);
                }
            }
        }
        return list;
    }

    private boolean compare(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if (s.val != t.val) return false;
        if (!compare(s.left, t.left) || !compare(s.right, t.right)) return false;
        return true;
    }
}

结果

subtree-of-another-tree-1