110.平衡二叉树

平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

思路：递归后序遍历求高度

递归三部曲：

1.返回值的参数：因为返回二叉树的高度，所以int（如果中间判断高度差大于1，返回-1），遍历二叉树需要root根节点

// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
int getHeight(TreeNode* node)

2.递归终止条件：if(node==null) return 0;

if (node == NULL) {
    return 0;
}

3.单层递归逻辑：先向左子节点遍历求leftheight,再向右子节点遍历求rightheight,如果求出高度差大于1，就return-1；如果不大于以result=1+max(leftheight,rightheight).

int leftHeight = getHeight(node->left); // 左
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right); // 右
if (rightHeight == -1) return -1;

int result;
if (abs(leftHeight - rightHeight) > 1) {  // 中
    result = -1;
} else {
    result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度
}

return result;

257. 二叉树的所有路径

思路：

本题涉及到回溯的算法，运用前序遍历，用一个vector容器来装当前遍历的路径，当你遍历到叶子节点的时候，就证明这条路径已经走到头了，这时候需要使用回溯，向上一个结点走，看是否能够走右边方向，如果不能就继续将上一个结点走，每次向上一个结点走的时候，都将当前节点的值从容器中弹出（这就叫回溯）。

递归三部曲：

1.确定参数和返回值：涉及到遍历所以需要传入根节点，需要一个vector<int>path来装经过结点的值(也就是路径）。需要一个vector<string>result,每次遍历完一条路径的时候，将这条路径压入result

404.左叶子之和

左叶子结点的定义：结点A的左孩子不为空，但是左孩子的左右孩子都为空，那么是左叶子结点

思路：

求左叶子结点的精髓在于找到左叶子节点的上一个结点进行判断，if(node->left!=null&&node->left->left==null&&node->left->right==null),左叶子结点在当前节点是不可判断的，只有在他的上一个结点才可以判断是否是左叶子节点。使用后序遍历求左叶子之和。

递归三部曲：

1.返回值和参数：返回值是左叶子之和，所以int，遍历需要root.

2.递归终止条件：

if (root == NULL) return 0;
if (root->left == NULL && root->right== NULL) return 0; //其实这个也可以不写，如果不写不影响结果，但就会让递归多进行了一层。

3.单层逻辑：

int leftValue = sumOfLeftLeaves(root->left);    // 左
if (root->left && !root->left->left && !root->left->right) {
    leftValue = root->left->val;
}
int rightValue = sumOfLeftLeaves(root->right);  // 右

int sum = leftValue + rightValue;               // 中
return sum;