小企业网站价格,沈阳网站建设哪家做得好啊,电子商务平台系统,塘厦 网站建设 百度推广【问题描述】
给定两个非空二叉树 s 和 t#xff0c;检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。示例 1:
给定的树 s:3/ \4 5/ \1 2
给定的树 t#xff1a;4 / \1 2
返回…【问题描述】
给定两个非空二叉树 s 和 t检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。示例 1:
给定的树 s:3/ \4 5/ \1 2
给定的树 t4 / \1 2
返回 true因为 t 与 s 的一个子树拥有相同的结构和节点值。
【解答思路】
1. 遍历 深度优先遍历
树的包含思路
是否相同的树思路
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public boolean isSubtree(TreeNode s, TreeNode t) {if (t null) return true; // t 为 null 一定都是 trueif (s null) return false; // 这里 t 一定不为 null, 只要 s 为 null肯定是 falsereturn isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);}/*** 判断两棵树是否相同*/public boolean isSameTree(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;return isSameTree(s.left, t.left) isSameTree(s.right, t.right);}
}
【总结】
1. 树 多用递归遍历 树的递归遍历过程是dfs
2. 二叉树遍历
前序遍历 先输出当前结点的数据再依次遍历输出左结点和右结点中序遍历 先遍历输出左结点再输出当前结点的数据再遍历输出右结点后续遍历 先遍历输出左结点再遍历输出右结点最后输出当前结点的数据
参考链接https://leetcode-cn.com/problems/same-tree/solution/hua-jie-suan-fa-100-xiang-tong-de-shu-by-guanpengc/ 参考链接https://leetcode-cn.com/problems/subtree-of-another-tree/solution/572java-di-gui-pan-duan-zi-shu-yu-tshi-fou-xiang-d/
