框架

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

alt

前序位置的代码在刚刚进入一个二叉树节点的时候执行，此时可以利用父节点的结果信息，可以通过遍历解决问题。
后序位置的代码在将要离开一个二叉树节点的时候执行，此时可以利用子节点的结果信息，可以通过递归解决问题。
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

练习

力扣 104. 二叉树的最大深度

class Solution {
    private int res = 0;
    private int depth = 0;

    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    private 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--;
    }
}

通过前序遍历，获取每层的深度，得到树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int l = maxDepth(root.left);
        int r = maxDepth(root.right);

        return Math.max(l, r) + 1;
    }
}

通过后序遍历，根据子树的深度，得到当前树的最大深度

力扣 543. 二叉树的直径

class Solution {
    // 记录最大直径的长度
    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);
    }

}

经过子树的最大直径，依赖左右子树的最大深度，故可以采用后序遍历

参考：

https://labuladong.gitee.io/algo/1/6/

Home

算法练习：二叉树遍历，前中后

框架

练习

Search

Table of Contents