Snap面经题目:count number of the same subtrees

0002505492

题目:

给一个树的root node,返回same subtree及个数:

给一个树的root node,返回same subtree及个数:
/*
                    10
                /        \
            8                3.
          /  \            /     \
         4    5        8           5
             /       /   \        /
            3       4     5      3. 
                         /. 
                        3
      Expects:
             8
            / \
           4   5      Count: 2
              /
             3

             5.
            /         Count: 3. 
           3
    */

思路:
使用postorder traverse,注意null节点返回“*”

代码:

import java.util.*;
class TreeNode
{
	public TreeNode left, right;
	public String  val;
	public TreeNode(String val)
	{
		this.val = val;
	}
}
public class Solution {

	public static TreeNode buildTree(String[] input)
	{
		int index = 0;
		TreeNode root = new TreeNode(input[index++]);
		Queue queue = new LinkedList<>();
		queue.offer(root);
		while(index < input.length)
		{
			
			int size = queue.size();
			for(int i = 0; i< size; i++)
			{
				TreeNode t = queue.poll();
				if(index >= input.length) return root;
				if(!input[index].equals("*"))
				{
					t.left = new TreeNode(input[index]);
					queue.offer(t.left);
				}
				index++;
				if(index >= input.length) return root;
				if(!input[index].equals("*"))
				{
					t.right = new TreeNode(input[index]);
					queue.offer(t.right);
				}
				index++;
				if(index >= input.length) return root;
			}
		}
		return root;
	}
	static HashMap sameSubtree(TreeNode root)
	{
		HashMap res = new HashMap<>();
		Map map = new HashMap<>();
		postorder(root, map, res);
		return res;
	}
	public static String postorder(TreeNode root, Map map,HashMap res)
	{
		if(root == null) return "*";
		String str = "";
		str += postorder(root.left, map, res);
		str += postorder(root.right, map, res);
		str += root.val;
		if(!map.containsKey(str))
		{
			map.put(str, root);
			res.put(root, 1);
		}
		else res.put(map.get(str), res.get(map.get(str))+1);
		return str;
	}
	public static void traverse(TreeNode t)
	{
		if(t == null) return;
		traverse(t.left);
		traverse(t.right);
		System.out.print(t.val+" ");
	}
	public static void main(String[] args)
	{
		String[] input = {"10", "8", "3", "4", "5", "8", "5", "*", "*", "3", "*", "4", "5", "3", "*", "*", "*", "*", "*","3"};
//		String[] input = {"1", "2", "3", "1", "2", "3", "4"};
		TreeNode root = buildTree(input);
		HashMap res = sameSubtree(root);
		for(TreeNode t : res.keySet())
		{
			System.out.println("traverse: ");
			traverse(t);
			System.out.println("count = " + res.get(t));
		}
		
	}
}

代码输出:
traverse:
3 count = 3
traverse:
4 3 5 8 3 5 3 count = 1
traverse:
4 3 5 8 4 3 5 8 3 5 3 10 count = 1
traverse:
4 3 5 8 count = 2
traverse:
4 count = 2
traverse:
3 5 count = 3

553total visits,2visits today