DFS一般的流程是这样的：从一个点出发，遍历其中一个邻居节点w, 然后接着遍历w的一个邻居节点，当遍历到最后一个节点之后，回退回上一个已经被遍历过的节点，接着遍历这个节点的未被遍历的节点，依次循环，直到遍历完所有的点为止。

Maximum Depth of N-ary Tree

Given a n-ary tree, find its maximum depth.The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

image.png
image.png
image.png
image.png

比较常规，用递归实现DFS的思路

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root)
            return 0;
        int max_depth = 1;
        DFS(root,1,max_depth);
        return max_depth;
    }

    void DFS(Node *node, int depth, int &max_depth){
        if(!node) return;
        if((node->children).empty())
            max_depth = max(depth,max_depth);

        for(auto tmp_node:node->children)
            DFS(tmp_node,depth+1,max_depth);
    }
};

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],return its depth = 3.

image.png

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int max_depth = 0;
        DFS(root,1,max_depth);
        return max_depth;
    }

    void DFS(TreeNode *root, int depth, int &max_depth){
        if(!root) return;
        if(!root->left || root->right)
            max_depth = max(depth,max_depth);

        DFS(root->left,depth+1,max_depth);
        DFS(root->right,depth+1,max_depth);
    }
};

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

image.png