首页 > 代码库 > 572. 是否为另一棵二叉树的子树 Subtree of Another Tree

572. 是否为另一棵二叉树的子树 Subtree of Another Tree

2024-10-02 17:12:39   214人阅读

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
Return false.

题意：判断一棵二叉树是否为另一棵二叉树的子树
解法：先序遍历二叉树，并生成字符串（用#表示孩子节点是否为null的情况），判断字符串的包含关系

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left;
  6.  *     public TreeNode right;
  7.  *     public TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public bool IsSubtree(TreeNode s, TreeNode t) {
  12.     	string s1 = Tree2String(s);
  13.     	string s2 = Tree2String(t);
  14.     
  15.     	return s1.Contains(s2) || s2.Contains(s1);
  16.     }
  17.     
  18. 	static public string Tree2String(TreeNode root) {
  19. 		if (root == null) {
  20. 			return "";
  21. 		}
  22. 		StringBuilder sb = new StringBuilder();
  24. 		Stack<TreeNode> stack = new Stack<TreeNode>();
  25. 		TreeNode current = root;
  27. 		stack.Push(current);
  29. 		while (stack.Count != 0) {
  30. 			TreeNode popelem = stack.Pop();
  31. 			/**
  32. 			 * 用#表示孩子节点是否为null的情况
  33. 			 * 用","号分隔节点是防止"12##"和"2##"这种情况
  34. 			 * ",12##",",2##"
  35. 			 */
  36. 			if (popelem == null) {
  37. 				sb.Append("#");
  38. 			} else {
  39. 				sb.Append(popelem.val);
  40. 			}
  41. 			if (popelem != null) {
  42. 				stack.Push(popelem.right);
  43. 				stack.Push(popelem.left);
  44. 			}
  45. 		}
  47. 		return sb.ToString();
  48. 	}
  49. }





null


572. 是否为另一棵二叉树的子树 Subtree of Another Tree


联系
我们