目錄
一、引言
二、判斷兩棵二叉樹是否相同
思路
代碼實現
注意點
三、二叉樹的中序遍歷
思路
代碼實現
注意點
四、判斷一棵樹是否為另一棵樹的子樹
思路
代碼實現
注意點
?編輯
五、補充
一、引言
作者主頁：共享家9527-CSDN博客
作者代碼倉庫：
Study in the first semester of college.c: 大一下學期學習，主要內容為個人學習過程記錄
2025寒假C語言學習: 學習記錄
在算法學習和面試準備中，二叉樹相關題目是常見且重要的類型。本文將結合小米面試真題以及經典的二叉樹算法題，分享解題思路、代碼實現以及一些需要注意的點。
二、判斷兩棵二叉樹是否相同
思路
采用遞歸的方式，從根節點開始比較。如果兩個節點都為空，說明它們相同；如果其中一個為空，另一個不為空，則不同；如果兩個節點值不同，也不同。然后遞歸地比較它們的左子樹和右子樹。
代碼實現
cbool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL) {return true;}if(p==NULL||q==NULL) {return false;}if(p->val!=q->val) {return false;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}注意點
1.?遞歸終止條件的判斷很關鍵，要先判斷兩個節點是否都為空，再判斷單個節點為空的情況。
2.?比較節點值時，注意數據類型的一致性。
三、二叉樹的中序遍歷
思路
中序遍歷的順序是左子樹、根節點、右子樹。通過遞歸的方式，先遍歷左子樹，然后將根節點的值存入結果數組，最后遍歷右子樹。在實現時，需要計算樹的節點數，以便為結果數組分配空間。
代碼實現
?
cvoid midtree(struct TreeNode* root,int* arr,int* returnSize) {if(root==NULL) {return;}midtree(root->left,arr,returnSize);arr[(* returnSize)++]=root->val;midtree(root->right,arr,returnSize);}int treesize(struct TreeNode* root) {if(root==NULL) {return 0;}return treesize(root->left)+treexize(root->right)+1;}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=0;int n=treesize(root);int *arr=(int*)malloc(sizeof(int)*n);midtree(root,arr,returnSize);return arr;}注意點
1.?遞歸函數中對數組和元素個數的操作要注意順序和邊界。
2.?使用?malloc?分配內存后，調用者需要負責釋放內存，避免內存泄漏。
四、判斷一棵樹是否為另一棵樹的子樹
思路
先判斷當前兩棵樹是否相同（利用前面的?isSameTree?函數），如果相同則返回?true?；如果不同，則遞歸地在原樹的左子樹和右子樹中繼續查找是否存在與子樹相同的結構。
代碼實現
cbool isSameTree(struct TreeNode* p, struct TreeNode* q) {// 同前面判斷兩棵樹相同的代碼}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if(root==NULL) {return false;}if(isSameTree(root,subRoot)) {return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}注意點
1.?遞歸調用時，要注意對空指針的處理，避免空指針異常。
2.?邏輯或?||?的使用，只要在左子樹或右子樹中找到匹配的子樹即可。
五、補充
1.?二叉樹相關題目中，遞歸是常用的方法，但也可以使用棧等數據結構實現非遞歸版本，在時間和空間復雜度上可能會有所不同。
2.?在面試中，除了寫出正確的代碼，還要能夠清晰地闡述解題思路和時間、空間復雜度分析。
通過對這些二叉樹算法題的學習和實踐，我們能更好地掌握二叉樹的結構和操作，為應對算法面試和實際開發中的問題打下堅實基礎。
