最近在看二叉树的算法，我觉得有点迷迷糊糊，就是那种一看就会，一写就费。我有点很奇怪的感觉，就感觉二叉树的很多问题，其实在于一步一步的遍历（或者称为迭代，或者是递归方法），然后在遍历的基础上进行逻辑（业务）操作。
首先在这讲一下递归。
递归有三部曲：
一. 确定函数参数，确定函数的返回值类型。
二. 确定终止条件
三.确定单层遍历的逻辑
下面，我们以平衡二叉树的算法进行在明确。
给定一个二叉树，判断它是否是 平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4] 输出：false
示例 3：
输入：root = [] 输出：true
算法解析：二叉树就是在递归（遍历）的基础上进行业务操作。
一：确定函数参数，确定函数的返回值类型。
int getDepth(TreeNode* root)；
二. 确定终止条件
if (root == nullptr) return 0;
当遇到这个说明节点已经被遍历完了，可以返回0了；
三.确定单层遍历的逻辑
还记得二叉树就是在递归（遍历）的基础上进行业务操作，重要的事情讲三遍！！
遍历类型有：前序，中序，后序，层次。具体的遍历顺序看具体的场景。
int leftHeight = getDepth(root->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getDepth(root->right); //右
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1; // 中
return 1 + max(leftHeight, rightHeight);
三部曲已经完成！下面是具体的过程：
#include <iostream>
#include <algorithm>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int getDepth(TreeNode* root) {
if (root == nullptr) return 0;
int leftHeight = getDepth(root->left);
if (leftHeight == -1) return -1;
int rightHeight = getDepth(root->right);
if (rightHeight == -1) return -1;
if (abs(leftHeight - rightHeight) > 1) return -1;
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getDepth(root) != -1;
}
};
int main() {
// Usage example
Solution solution;
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(6);
cout << (solution.isBalanced(root) ? "Balanced" : "Not Balanced") << endl;
return 0;
}