剑指55：二叉树的深度

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    DFS，递归实现
*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
		if (pRoot == nullptr) return 0;
		
		int leftDepth = TreeDepth(pRoot->left);
    	int rightDepth = TreeDepth(pRoot->right);
    	return max(leftDepth, rightDepth) + 1;
    }
};

/*
    BFS，迭代
*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
		if (pRoot == nullptr) return 0;

		queue<pair<TreeNode*, int>> que;
		que.push(make_pair(pRoot, 1));
		int maxDepth = 1;
		while (!que.empty()) {
			TreeNode* curNode = que.front().first;
			int curDepth = que.front().second;
			que.pop();
			if (curNode) {
				maxDepth = max(maxDepth, curDepth);
				que.push({ curNode->left, curDepth + 1 });
				que.push({ curNode->right, curDepth + 1 });
			}
		}
		
		return maxDepth;
    }
};

C++ 代码 - leetcode

/*
    回溯算法思路
*/
class Solution {
private:
    int depth = 0;
    int res = 0;

public:
    int calculateDepth(TreeNode* root) {
        traverse(root);
        return res;
    }

    // 遍历二叉树
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // 前序遍历位置
        depth ++;
        // 遍历的过程中记录最大深度
        res = std::max(res, depth);
        traverse(root->left);
        traverse(root->right);
        // 后序遍历位置
        depth --;
    }
};

/*
	动态规划思路
*/
class Solution {
public:
    // 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
    int calculateDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int leftMax = calculateDepth(root->left);
        int rightMax = calculateDepth(root->right);
        // 根据左右子树的最大深度推出原二叉树的最大深度
        return 1 + std::max(leftMax, rightMax);
    }
};