链表、二叉树—递归遍历框架

注意：

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点

前序：刚刚进入一个节点执行
中序：左子树全部执行完，准备执行右子树前
后续：离开节点前执行

二叉树前中后序遍历框架

void traverse(TreeNode head){
    if(head==null){
      return;
    }
    //前序遍历
    traverse(head.left);
    //中序遍历
    traverse(head.right);
    //后续遍历
}

链表递归遍历框架

void traverse(ListNode head){
    if(head==null){
        return head;
    }
    //正序遍历
    traverse(head.next);
    //逆序遍历
}

不说废话先做题

class Solution {
    //保存返回结果
    int res=0;
    //记录二叉树层数
    int floor=0;
    void  traverse(TreeNode head){
        if(head==null){
            res=Math.max(floor,res);
            return;
        }
        //第一次进入节点 我就开始floor++
        floor++;

        traverse(head.left);
        traverse(head.right);

        //离开节点的时候floor--
        floor--;
    }
    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }
}

递归版本分解问题

class Solution {
    int max(TreeNode head){
        if(head==null){
            return 0;
        }
        int maxLeft=max(head.left);
        int maxRight=max(head.right);
        return Math.max(maxLeft,maxRight)+1;
    }
    public int maxDepth(TreeNode root) {
        return max(root);
    }
}