⼆叉树题⽬的递归解法可以分两类思路

  • 第⼀类是遍历⼀遍⼆叉树得出答案
  • 第⼆类是通过分解问题计算出答案。

快速排序就是二叉树的前序遍历，归并排序是二叉树的后序遍历。

二叉树遍历框架

  1. void traverse(TreeNode root) {
  2.     if (root == null) {
  3.         return;
  4.     }
  5.     // 前序位置
  6.     traverse(root.left);
  7.     // 中序位置
  8.     traverse(root.right);
  9.     // 后序位置
  10. }

前中后序遍历

前中后序是遍历⼆叉树过程中处理每⼀个节点的三个特殊时间点，绝不仅仅是三个顺序不同的
List：
前序位置的代码在刚刚进⼊⼀个⼆叉树节点的时候执⾏；
后序位置的代码在将要离开⼀个⼆叉树节点的时候执⾏；
中序位置的代码在⼀个⼆叉树节点左⼦树都遍历完，即将开始遍历右⼦树的时候执⾏。
你注意本⽂的⽤词，我⼀直说前中后序「位置」，就是要和⼤家常说的前中后序「遍历」有所区别：你可以
在前序位置写代码往⼀个 List ⾥⾯塞元素，那最后得到的就是前序遍历结果；但并不是说你就不可以写更复
杂的代码做更复杂的事。
image.png

144. 二叉树的前序遍历

先序遍历可以想象成，小仙儿从树根开始绕着整棵树的外围转一圈，经过结点的顺序就是先序遍历的顺序
先序遍历结果：ABDHIEJCFKG
image.png

  1. List<Integer> res = new LinkedList<>();
  3. // 返回前序遍历结果
  4. List<Integer> preorderTraverse(TreeNode root) {
  5.     traverse(root);
  6.     return res;
  7. }
  9. // 二叉树遍历函数
  10. void traverse(TreeNode root) {
  11.     if (root == null) {
  12.         return;
  13.     }
  14.     // 前序位置
  15.     res.add(root.val);
  16.     traverse(root.left);
  17.     traverse(root.right);
  18. }

94. 二叉树的中序遍历

中序遍历可以想象成，按树画好的左右位置投影下来就可以了
中序遍历结果：HDIBEJAFKCG
image.png

LinkedList<Integer> res = new LinkedList<>();

public List<Integer> inorderTraversal(TreeNode root) {
    traverse(root);
    return res;
}

void traverse(TreeNode root){
    if(root == null)
        return;
    //前序位置
    traverse(root.left);
    //中序位置
    res.add(root.val);
    traverse(root.right);
    //后序位置
}

145. 二叉树的后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。
围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。
后序遍历结果：HIDJEBKFGCA
image.png

LinkedList<Integer> res = new LinkedList<>();

public List<Integer> postorderTraversal(TreeNode root) {
    traverse(root);
    return res;
}

void traverse(TreeNode root){
    if(root == null)
        return;
    //前序位置
    traverse(root.left);
    //中序位置
    traverse(root.right);
    //后续位置
    res.add(root.val);
}

144. 二叉树的前序遍历

就是一个很简单的前序遍历的代码。

LinkedList<Integer> res = new LinkedList<>();

public List<Integer> preorderTraversal(TreeNode root) {
    traverse(root);
    return res;
}

void traverse(TreeNode root){
    if(root == null)
        return;
    //前序位置
    res.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

104. 二叉树的最大深度

在一开始，我们就定义了二叉树问题分为两类，第⼀类是遍历⼀遍⼆叉树得出答案，第⼆类是通过分解问题计算出
答案。

遍历解法

很明显，104这道题我们遍历一遍二叉树，用外部变量记录每一个节点所在的深度，取最大值就可以得到最大深度，这就是遍历二叉树计算答案的思路。

//记录最大深度
int res = 0;
//记录遍历到节点的深度
int depth = 0;

//主函数
public int maxDepth(TreeNode root) {
    traverse(root);
    return res;
}

//二叉树遍历框架
void traverse(TreeNode root){
    if(root == null)
        return;
    //前序位置
    depth++;
    if(root.left == null && root.right == null){
        //到达叶子节点，更新最大深度
        res = Math.max(res, depth);
    }
    traverse(root.left);
    //中序位置
    traverse(root.right);
    //后续位置
    depth--;
}

这里需要理解是为什么在前序位置递增depth，在后续位置depth递减1。因为，前序位置是进入一个节点的时候执行，后续位置是将要离开一个节点的时候执行，depth 记录当前递归到的节点深度。我们把 traverse 理解成在二叉树上游走的指针，所以要这样维护 depth 来确保指向的每一个节点的深度是正确的。

记录最大深度
记录遍历到的节点的深度

traverse root
返回res

二叉树遍历框架
    前序位置
    depth递增1
    如果到达叶子节点，更新最大深度
    traverse左节点

    中序位置
    traverse右节点

    后续位置
    depth递减1

分解解法

// 定义：输⼊根节点，返回这棵⼆叉树的最⼤深度
int maxDepth(TreeNode root) {
    if (root == null) {
    return 0;
    }
    // 利⽤定义，计算左右⼦树的最⼤深度
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    // 整棵树的最⼤深度等于左右⼦树的最⼤深度取最⼤值，
    // 然后再加上根节点⾃⼰
    int res = Math.max(leftMax, rightMax) + 1;
    return res;
}

543. 二叉树的直径

前序位置是刚刚进入节点的时候执行，后续位置是即将离开节点的时候执行。这意味着，前序位置的代码只能从函数参数中获取父节点传递过来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的参数。
换句话说，一旦我们发现题目和子树相关，那大概率要给函数设置合理的定义和返回值，在后续位置写代码了。

未优化版

这里可以看到，traverse中会调用递归函数，maxDepth也要遍历子树的所有节点，所以这个版本很差。这个未优化版，是在前序位置计算树的深度。

// 记录最大直径的长度
int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    // 对每个节点计算直径，求最大直径
    traverse(root);
    return maxDiameter;
}

// 遍历二叉树
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 对每个节点计算直径
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    int myDiameter = leftMax + rightMax;
    // 更新全局最大直径
    maxDiameter = Math.max(maxDiameter, myDiameter);

    traverse(root.left);
    traverse(root.right);
}

// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    return 1 + Math.max(leftMax, rightMax);
}

优化版本

未优化版，是在前序位置计算树的深度，但是前序位置无法获取子树的信息，所以只能让每个节点调用maxDepth函数去计算每个子树的深度。所以我们把计算「直径」的逻辑代码放在后续位置，准确的说是放在maxDepth的后续位置，因为maxDepth的后续位置是知道左右子树的最大深度的。
讲到这⾥，照应⼀下前⽂：遇到⼦树问题，⾸先想到的是给函数设置返回值，然后在后序位置做⽂章。

//记录最大直径的长度
int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    //对每个节点计算直径，求最大直径
    maxDepth(root);
    return maxDiameter;
}

//计算二叉树的最大深度
int maxDepth(TreeNode root){
    if(root == null){
        return 0;
    }
    int leftMax = maxDepth(root.left);
    int rightMax = maxDepth(root.right);
    //后续位置，计算最大直径
    int myDiameter = leftMax + rightMax;
    maxDiameter = Math.max(maxDiameter, myDiameter);

    return 1 + Math.max(leftMax, rightMax);
}

剑指 Offer 55 - I. 二叉树的深度

与104题目相同。