---

樹形dp問題

求解這個問題需要用到我們在基礎班上學到的從節點的左子樹和右子樹上拿信息的方法。
求最大距離主要分為兩種情況：1.當前節點參與最大距離的求解；2.當前節點不參與最大距離的求解；
1.當前節點參與最大距離的求解的話，最大距離為左子樹的高度加上右子樹的高度加一；
2.當前節點不參與最大距離的求解的話，最大距離為左子樹的最大距離與右子樹的最大距離的最大值；
取這兩種情況的最大值即為以當前節點為根節點的樹的最大距離

核心代碼

---

我們可以根據題意列出：
當某位員工參與時，派對的快樂值為其快樂值加上其直接下級員工不參與時的快樂值之和
當某位員工不參與時，派對的快樂值為其直接下級員工參與時的快樂值與其直接下級員工不參與時的快樂值的最大值之和。

代碼：

Morris遍歷

由上述規則可知：Morris遍歷一共會來到某個節點兩次，第一次到達某個節點時，其會找到其左子樹的最右節點，將該節點的右指針指向當前節點，當其第二次來到節點時，其會將其左子樹的最右節點指向空。由此我們便可以利用這一特點進行先序遍歷和中序遍歷。

先序遍歷

中序遍歷：

由于Morris遍歷無法第三次回到某個節點，后序遍歷會比較復雜：當第二次來到自己的時候，逆序打印其左樹的右邊界。

---