首先按照普通二叉樹的邏輯來求。

這道題目的遞歸法和求二叉樹的深度寫法類似， 而迭代法，二叉樹：層序遍歷登場！?(opens new window)遍歷模板稍稍修改一下，記錄遍歷的節點數量就可以了。

遞歸遍歷的順序依然是后序（左右中）。

完全二叉樹只有兩種情況，情況一：就是滿二叉樹，情況二：最后一層葉子節點沒有滿。

對于情況一，可以直接用 2^樹深度 - 1 來計算，注意這里根節點深度為1。

對于情況二，分別遞歸左孩子，和右孩子，遞歸到某一深度一定會有左孩子或者右孩子為滿二叉樹，然后依然可以按照情況1來計算。

?對于情況二，如果一開始沒有找到滿二叉樹，就會去+1，然后從左右節點再去找二叉樹，這樣子遞歸，所以不用擔心會漏節點。我們來看兩種方法的代碼

class Solution {// 通用遞歸解法public int countNodes(TreeNode root) {if(root == null) {return 0;}return countNodes(root.left) + countNodes(root.right) + 1;}
}

class Solution {/*** 針對完全二叉樹的解法** 滿二叉樹的結點數為：2^depth - 1*/public int countNodes(TreeNode root) {if (root == null) return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0, rightDepth = 0; // 這里初始為0是有目的的，為了下面求指數方便while (left != null) {  // 求左子樹深度left = left.left;leftDepth++;}while (right != null) { // 求右子樹深度right = right.right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相當于2^2，所以leftDepth初始為0}return countNodes(root.left) + countNodes(root.right) + 1;}
}

此時大家應該明白了既然要求比較高度，必然是要后序遍歷。

遞歸三步曲分析：

1. 明確遞歸函數的參數和返回值

參數：當前傳入節點。 返回值：以當前傳入節點為根節點的樹的高度。

那么如何標記左右子樹是否差值大于1呢？

如果當前傳入節點為根節點的二叉樹已經不是二叉平衡樹了，還返回高度的話就沒有意義了。

所以如果已經不是二叉平衡樹了，可以返回-1 來標記已經不符合平衡樹的規則了。

private int getHeight(TreeNode root)

2.明確終止條件

遞歸的過程中依然是遇到空節點了為終止，返回0，表示當前節點為根節點的樹高度為0

if (root == null) {return 0;}

3.明確單層遞歸的邏輯

如何判斷以當前傳入節點為根節點的二叉樹是否是平衡二叉樹呢？當然是其左子樹高度和其右子樹高度的差值。

分別求出其左右子樹的高度，然后如果差值小于等于1，則返回當前二叉樹的高度，否則返回-1，表示已經不是二叉平衡樹了。

我們來看完整代碼

class Solution {/*** 遞歸法*/public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}private int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);if (leftHeight == -1) {return -1;}int rightHeight = getHeight(root.right);if (rightHeight == -1) {return -1;}// 左右子樹高度差大于1，return -1表示已經不是平衡樹了if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}
}

這道題目要求從根節點到葉子的路徑，所以需要前序遍歷，這樣才方便讓父節點指向孩子節點，找到對應的路徑。

在這道題目中將第一次涉及到回溯，因為我們要把路徑記錄下來，需要回溯來回退一個路徑再進入另一個路徑。

前序遍歷以及回溯的過程如圖：

?1.遞歸函數參數以及返回值

我們需要傳入一個根節點root，記錄每一條路徑path，和存放結果集的result，這里遞歸不需要返回值

private void traversal(TreeNode root, List<Integer> paths, List<String> res)

2.確定終止條件

我們找到了一個葉子節點，也就結束這一次遞歸

if (cur->left == NULL && cur->right == NULL) {終止處理邏輯
}

我們再來看一下終止邏輯

// 輸出StringBuilder sb = new StringBuilder();// StringBuilder用來拼接字符串，速度更快for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));// 記錄最后一個節點res.add(sb.toString());// 收集一個路徑return;

我們用StringBuilder來拼接字符串，然后我們開始循環遍歷path將其存入sb中，注意不要遍歷到最后一個元素，因為題目要求“->”，所以我們遍歷到倒數第二個元素即可，然后將再單獨添加卒子后一個元素，最后將拼接的sb添加給res，然后結束方法

3.確定單層遞歸邏輯

因為這道題是前序遍歷，我們需要先處理中間節點，中間節點就是我們要記錄的路徑上的節點，先放進path中

path.push_back(cur->val);

然后進行左右的遞歸回溯，為什么我們需要將判斷葉子節點放在遍歷之前，因為如果是葉子節點，我們直接退出，然后進行返回結果。

我們來看代碼

/方式一
class Solution {/*** 遞歸法*/public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();// 存最終的結果if (root == null) {return res;}List<Integer> paths = new ArrayList<>();// 作為結果中的路徑traversal(root, paths, res);return res;}private void traversal(TreeNode root, List<Integer> paths, List<String> res) {paths.add(root.val);// 前序遍歷，中// 遇到葉子結點if (root.left == null && root.right == null) {// 輸出StringBuilder sb = new StringBuilder();// StringBuilder用來拼接字符串，速度更快for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));// 記錄最后一個節點res.add(sb.toString());// 收集一個路徑return;}// 遞歸和回溯是同時進行，所以要放在同一個花括號里if (root.left != null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right != null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}}

如果該節點的左節點不為空，該節點的左節點的左節點為空，該節點的左節點的右節點為空，則找到了一個左葉子，判斷代碼如下：?

if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {左葉子節點處理邏輯
}

1.確定終止條件

如果遍歷到空節點，那么左葉子值一定是0，只有當前遍歷的節點是父節點，才能判斷其子節點是不是左葉子。 所以如果當前遍歷的節點是葉子節點，那其左葉子也必定是0，那么終止條件為：

if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0; //其實這個也可以不寫，如果不寫不影響結果，但就會讓遞歸多進行了一層

?2.確定單層遞歸的邏輯

當遇到左葉子節點的時候，記錄數值，然后通過遞歸求取左子樹左葉子之和，和 右子樹左葉子之和，相加便是整個樹的左葉子之和。

int leftValue = sumOfLeftLeaves(root.left);    // 左if (root.left != null && root.left.left == null && root.left.right == null) { // 左子樹就是一個左葉子的情況leftValue = root.left.val;}int rightValue = sumOfLeftLeaves(root.right);  // 右int sum = leftValue + rightValue;              // 中return sum;

我們來看完整代碼

class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) return 0;if (root.left == null && root.right == null) return 0;int leftValue = sumOfLeftLeaves(root.left);    // 左if (root.left != null && root.left.left == null && root.left.right == null) { // 左子樹就是一個左葉子的情況leftValue = root.left.val;}int rightValue = sumOfLeftLeaves(root.right);  // 右int sum = leftValue + rightValue;              // 中return sum;}
}