今天繼續二叉樹的遞歸套路。 一、最低公共祖先 給定一個二叉樹的頭節點，和另外兩個節點a、b，返回a、b的最低公共祖先。 最低公共祖先定義：a、b往上找，第一個相同的祖先（這個公共祖先也可能是a或b自己） 1、遞歸套路思路 對於二叉樹中的任意一個節點X，以及兩個節點a、b，a和b的最低公共祖先分為兩種情況。 （1）與X無關，即最低公共祖先不是X a、b在左樹中某個點匯聚了 a、b在右樹中某個點匯聚了
今天繼續二叉樹的遞歸套路。 一、判斷是否是滿二叉樹 滿二叉樹定義：對於高度為h的二叉樹，節點數為（2^h - 1） 1、遞歸套路思路 根據滿二叉樹的定義可以知道，我們每次只需要獲取高度、節點數即可。 也就是每次從左子樹和右子樹中我們都需要 高度、節點數 兩個數據，最後再根據高度和節點數的關係判斷是否是滿二叉樹。所以可以定義如下的Info類 /** *@authorJava和算法學習：週一 */ p
本篇繼續來聊聊二叉樹的遞歸套路。 一、判斷二叉樹是否是搜索二叉樹 搜索二叉樹定義：二叉樹中的任意一個以X為頭的子樹，左子樹都比X小，右子樹都比X大。（經典的搜索二叉樹是沒有重複值的） 1、經典做法 中序遍歷，結果是遞增的，説明這是搜索二叉樹。 2、遞歸套路思路 分析任意一個以X為頭的子樹，滿足以X為頭的子樹是搜索二叉樹的條件（列出所有可能性） 1）左子樹是搜索二叉樹 2）右子樹是搜索二叉樹 3）左
二叉樹的基本套路我們已經很熟悉了，接下來我們聊聊二叉樹的遞歸套路，可以解決面試中絕大多數的二叉樹問題，尤其是樹型dp問題，其本質是利用遞歸遍歷二叉樹的便利性。 判斷二叉樹是否是完全二叉樹 1、經典寫法思路 （1）某個節點有右孩子無左孩子，則一定不是完全二叉樹 （2）當第一次遇到左右孩子不雙全的節點時，以後遇到的節點都是葉節點 2、遞歸套路思路 對於任意一顆子樹，判斷是否是完全二叉樹的條件（列出所有
