【問題描述】

給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結構和節點值的子樹。s 的一個子樹包括 s 的一個節點和這個節點的所有子孫。s 也可以看做它自身的一棵子樹。示例 1: 給定的樹 s:3/ \4 5/ \1 2 給定的樹 t：4 / \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/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第572题][另一个树的子树]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。