广东华星建设集团网站,工程建设项目管理系统平台,营销型网站的评价标准,外贸网站建设及优化ppt模块【问题描述】
给定两个非空二叉树 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/
