104.二叉树的最大深度

高度是节点到叶子节点的距离，相当于树站在地面上，深度是当前节点到二叉树顶点的距离.
后序求高度，处理逻辑在最后，当节点都遍历完后，子节点可以把自己的高度返回给父节点。
前序求深度，处理逻辑在最前，遍历时就动态更新每一步的深度值(需要一个全局参数来记录深度值的最大值)。这两题层序遍历做过了已经，这里用递归的方式，后序和前序。
有没有注意到，后序递归是int返回值类型，而前序是void类型深度由参数记录。

后序遍历求根节点的最大高度（二叉树的最大深度）

根节点的高度就是二叉树的最大深度。

//C++
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return maxHeight(root);
    }
    int maxHeight(TreeNode* cur) {
        if (cur == nullptr) return 0;
        int left = maxHeight(cur->left);
        int right = maxHeight(cur->right);
        int depth = max(left, right) + 1;
        return depth;
    }
};
//C#
public class Solution {
    public int MaxDepth(TreeNode root) {
        return MaxHeight(root);
    }
    public int MaxHeight(TreeNode cur) {
        if (cur == null) return 0;
        return Math.Max(MaxHeight(cur.left),MaxHeight(cur.right)) + 1;
    }
}

前序遍历

前序求深度，处理逻辑在最前，遍历时就动态更新每一步的深度值(需要一个全局参数来记录深度值的最大值)。depth如果是全局变量，注意回溯，如果是局部变量（作为参数）则不需要回溯，因为递归回退的时候实际上已经撤销了depth++。

随想录的做法起始值是1，只要在这一层递归提前对下一层递归的变量做了提前操作，结束递归调用的时候就要显式回溯，而我的做法是0，每一层递归只加我这一层的高度。
这一层的变量因为是全局变量或者引用或者为了方便下一层递归传参导致之后的递归影响了这一层的变量，那么就需要显示的进行回溯还原变量，如果不影响那就不用回溯，递归两层的变量本就不一样。

例子（day17求二叉树所有路径,提前对下一层进行了操作）： alt

从1开始（代表深度先+1），depth++提前算了下一层，要回溯。

alt

class Solution {
public:
    int result;
    int depth;
    int maxDepth(TreeNode* root) {
        result = INT_MIN;
        depth = 0;
        if (root == nullptr) return 0;
        getDepth(root);
        return result;
    }
    void getDepth(TreeNode* cur) {
        depth++;
        result = depth > result ? depth : result;
        if (cur->left == nullptr && cur->right == nullptr) return;
        if (cur->left != nullptr) {
          	//depth++;
            getDepth(cur->left);
            depth--;
        }
        if (cur->right != nullptr) {
          	//depth++;
            getDepth(cur->right);
            depth--;
        }
        return;
    }
};
//C#
public class Solution {
    int result;
    public int MaxDepth(TreeNode root) {
        result = 0;
        getDepth(root, 0);
        return result;
    }
    public void getDepth(TreeNode cur, int depth) {
        result = result > depth ? result : depth;
        if (cur == null) return;
        depth++;
        getDepth(cur.left, depth);
        getDepth(cur.right, depth);
        return;
    }
}

二刷考虑一下前序是不是比后序少遍历。

111.二叉树的最小深度

最小和最大不一样，注意最小深度是根节点到叶子节点的最小距离，而叶子结点必须保证有（不能是单叉的树），为空不是最小深度，所以在取min之前要判断，如果左右子树中有一个为空，那就选择另一个子树的最小深度，手动规避空陷阱。 alt

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return minHeight(root);
    }
    int minHeight(TreeNode* node) {
        if (node == nullptr) return 0;
        int left = minDepth(node->left);
        int right = minDepth(node->right);
        if (node->left == nullptr && node->right != nullptr) return 1 + right;
        if (node->left != nullptr && node->right == nullptr) return 1 + left;
        return min(left, right) + 1;//左右都为空和左右都不为空
    }
};

前序遍历（我还是喜欢全局变量，然后回溯）。

class Solution {
private:
    int result;
    int depth;
    void getdepth(TreeNode* node) {
        depth++;
        if (node->left == NULL && node->right == NULL) {
            result = min(depth, result);  
            return;
        }
        // 中 只不过中没有处理的逻辑
        if (node->left) { // 左
            getdepth(node->left);
            depth--;
        }
        if (node->right) { // 右
            getdepth(node->right);
            depth--;
        }
        return ;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        result = INT_MAX;
        depth = 0;
        getdepth(root);
        return result;
    }
};

222.完全二叉树的节点个数

普通二叉树前序和后序，层序的就不写了，这题主要考察完全二叉树的特性：最后一层左边是连续的，所以往下递归分总能全部分成满二叉树，而满二叉树的节点计算很简单2^n - 1，判定条件是左右递归深度一样，就不需要遍历内侧的节点了，能减时间复杂度。完全二叉树的节点个数->分成若干个满二叉树递归计算节点个数。因此只要判断是满二叉树，直接返回数量即可。单层递归逻辑是 = 左子树个数+右子树个数+1。

二刷巩固一下这里的递归三部曲，返回条件挺复杂的。

注意位运算优先级（得加括号）和n的实际含义（2左移n位实际上是2^（n + 1））。

//C++
class Solution {
public:
    int countNodes(TreeNode* root) {
        return doit(root);
    }
    int doit(TreeNode* cur) {
        if (cur == nullptr) return 0;
        TreeNode* left = cur->left;
        TreeNode* right = cur->right;
        int leftDepth = 0, rightDepth = 0;
        while (left) {
            left = left->left;
            leftDepth++;
        }
        while (right) {
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        int leftTreeNum = countNodes(cur->left);       // 左
        int rightTreeNum = countNodes(cur->right);     // 右
        int result = leftTreeNum + rightTreeNum + 1;    // 中
        return result;
    }
};
//C#
public class Solution {
    public int CountNodes(TreeNode root) {
        return doit(root);
    }
    int doit(TreeNode cur) {
        if (cur == null) return 0;
        int leftHeight = 0;
        int rightHeight = 0;
        TreeNode left = cur;
        TreeNode right = cur;
        while(left != null) {
            leftHeight++;
            left = left.left;
        }
        while(right != null) {
            rightHeight++;
            right = right.right;
        }
        if (leftHeight == rightHeight) return (2 << (leftHeight - 1)) - 1;

        return doit(cur.left) + doit(cur.right) + 1;

    }
}

利用完全二叉树的性质可以在返回条件上做剪枝，如果啥都不剪就是正常后序遍历，时间复杂度为O(n)。

public class Solution {
    public int CountNodes(TreeNode root) {
        return doit(root);
    }
    int doit(TreeNode cur) {
        if (cur == null) return 0;
        return doit(cur.left) + doit(cur.right) + 1;

    }
}

二刷

二叉树的最大深度

递归先序，后序层序都可以，递归时注意如果回溯不交给递归本身，而是使用引用的形式传参，那就要手动depth--，并且前后只回溯一次，因为只是当前层向上回溯一次depth-1即可。

注意，先序是在自顶向下dfs时就记录最大深度，而后序是在左右子树都搜索完后，自底向上返回更新高度，两者方向不一样，中序没法记录，因为此时左子树走完了，而右子树没走完，没法比较。

//先序
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int res = INT_MIN;
        int depth = 0;
        Doit(root, depth, res);
        return res;
    }
  	//手动回溯
    void Doit(TreeNode* cur, int& depth, int& res) {
        if (cur == nullptr) return;
        if (depth > res) res = depth;
        Doit(cur->left, depth, res);
        Doit(cur->right, depth, res);
        depth--;
    }
  	//自动回溯
      void Doit(TreeNode* cur, int depth, int& res) {
        if (cur == nullptr) return;
        depth++;
        if (depth > res) res = depth;
        Doit(cur->left, depth, res);
        Doit(cur->right, depth, res);
    }
};

后序遍历必须要用用有返回值返回类型来记录左右子树都搜索完毕时触底向上返回时底下每一层的最大高度结果，否则会丢失，举一反三，不能使用中序也是因为此时右子树还没有遍历，没法比较。

后序也有两种写法，可以按照高度从0开始往上返回累加，也可以往回返回时直接返回树的深度。

	//后序
    int maxDepth(TreeNode* root) {
        return Doit(root, 0);
    }
	//返回树的高度
    int Doit(TreeNode* cur, int depth) {
        if (cur == nullptr) return depth;
        int left = Doit(cur->left, depth++);
        int right = Doit(cur->right,depth++);
        return max(left, right);
    }
	//返回树的深度
    int maxHeight(TreeNode* cur) {
        if (cur == nullptr) return 0;
        int left = maxHeight(cur->left);
        int right = maxHeight(cur->right);
        int depth = max(left, right) + 1;
        return depth;
    }

二叉树的最小深度

注意，如果只把求最大深度的max改成min，会把单叉树的空左/右孩子计入更新（0产生干扰），是的最小值一直为1，遇到单叉树应该跳过继续向下搜索了，因此提前判断分支情况。

	//后序
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return Doit(root);
    }

    int Doit(TreeNode* cur) {
        if (cur->left == nullptr && cur->right == nullptr) return 1;
        else if (cur->left == nullptr) {
            return Doit(cur->right) + 1;
        } else if (cur->right == nullptr) {
            return Doit(cur->left) + 1;
        }
        int left = Doit(cur->left);
        int right = Doit(cur->right);
        return min(left, right) + 1;
    }
	//前序

如果用层序遍历的话，在第一次找到左右都为空的分支节点时，放入即可。

完全二叉树的节点个数

利用完全二叉树可以划分为满二叉树子树的特性，用后序会更精简。

普通二叉树的前序计算个数版本。
完全二叉树的O(log(n))版本，终止条件更复杂。

[代码随想录一刷&二刷] day16 二叉树