序言

学习随笔是本人对自己一天的自学回顾，由于本人是非科班出身，不懂很多cs的专业术语，所以难免会有些错误，望各位批评指正，本人定当悉心接受并立即改正。希望自己能够慢慢坚持下去，坚持转行的道路，坚持每天学习的输出。

刷题篇

LeetCode

1.题目

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

2.大致思路

因为对树不熟，所以第一时间只想着要遍历，但却不知道怎么遍历，服了自己。

二叉树的三种遍历方式：前序遍历，中序遍历，后序遍历。

这里明显是后序遍历。

在遍历二叉树时，还有一个重要的思想：递归。

在设计递归时，一定要注意递归出口。

看完这些，代码基本上就已经写完了。

3.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    if(root!=NULL){    //* 一直往下搜，搜到底即没有左右子树了，即此结点为叶子结点
        int a=maxDepth(root->left);
        int b=maxDepth(root->right);
        if(a>b) return a+1;
        else return b+1;
//* 后两句代码可以简写成  return (a>b) ? a+1:b+1;
    }
    return 0;
}

4.回顾知识点

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；

常见的 DFS ： 前序遍历、中序遍历、后序遍历；
常见的 BFS ： 层序遍历（即按层遍历）。

树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现。

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

利用栈实现后序遍历

用两个栈完成后序遍历

一个临时栈（起回溯作用），一个结果栈

原因：一个栈无法回溯

由于后序遍历是左——右——根，所以入栈应该是根——右——左

step1:从根结点开始，将当前结点同时入临时栈和结果栈，并遍历右子树

step2:当右子树遍历结束后，弹出临时栈栈顶结点，并遍历其左子树，继续step1步骤 （这里便是不停地根——右——左的过程）

step3:当所有结点都访问完，即最后访问的树节点为空且临时栈也为空时，主算法结束，依次弹出结果栈的结点