一、題目大意

給定一個二叉樹，找出其最大深度，

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，

說明: 葉子節點是指沒有子節點的節點，

示例：
給定二叉樹 [3,9,20,null,null,15,7]，

回傳它的最大深度 3 ，

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/maximum-depth-of-binary-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

二、解題思路

思路：求二叉樹的最大深度問題用深度優先搜索 Depth First Search，遞回的完美應用，

思路二：也可以用層序遍歷二叉樹，然后計數總層數，即為二叉樹的最大深度，需要注意的是while回圈中的for回圈的寫法，一定要將q.size()放在初始化里，而不能放在普快停止的條件中，因為q的大小是隨時變化的，所以放在停止條件中會出錯，

三、解題方法

3.1 Java實作-遞回

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

3.2 Java實作-層序遍歷

public class Solution2 {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ans = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            ans++;
            for (int i = q.size(); i > 0; i--) {
                TreeNode t = q.poll();
                if (t.left != null) {
                    q.offer(t.left);
                }
                if (t.right != null) {
                    q.offer(t.right);
                }
            }
        }
        return ans;
    }
}

四、總結小記

2022/9/5 做開發沒有需求設計那就是無窮災難的開端

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504409.html

標籤：其他

上一篇：參加了個演算法比賽，真是一言難盡啊