数据结构与算法-求二叉树的最大深度，总节点个数，叶子节点个数【九】

拼搏现实的明天。 2023-02-12 03:28 10阅读 0赞

标签（空格分隔）： 二叉树深度 节点

--------------------

对应着leetcode的题目编号是： 104，222

### 思路一 ###

这3个问题，最简单的办法就是定一个全局变量，然后遍历整棵树，最后对全局变量进行处理或者返回即可。【可以理解为自上而下，从根节点开始往下面走】

求二叉树最大深度：

var maxDepth = (root) => { 
         if (!root) return 0
         const arr = []
         // 遍历所有，直到叶子节点
         var helpFunc = (node, i = 1) => { 
             if (node) { 
                 if (!node.left && !node.right) { 
                     arr.push(i)
                 }
                helpFunc(node.left, i+1)
                helpFunc(node.right, i+1)
             }
         }
         helpFunc(root)
         return Math.max(...arr)
     }

求总节点个数

var countNodes = (root) => { 
        let i = 0;
        const helpFunc = (node) => { 
            if (node) { 
                i++
                helpFunc(node.left)
                helpFunc(node.right)
            }
        }
        helpFunc(root)
        return i
    };

求叶子节点个数：

var countLeafNodes = (root) => { 
        let i = 0
        const helpFunc = (node) => { 
            if (node ) { 
                if (!node.left && !node.right) { 
                    i++
                }
                helpFunc(node.left)
                helpFunc(node.right)
            }
        }
        helpFunc(root)
        return i
    }

### 思路二 ###

上面其实已经达到题目要求了，咱们尝试初始化在树的底层叶子节点来初始化数据，一层一层往上面返回。

求二叉树最大深度，从根节点开始，最大深度为 `Math.max（左子树的最大深度，右子树的最大深度比较）+ 1`；左子树的最大深度, 仍然是相对于左子树的根节点来说`Math.max（左子树的最大深度，和右子树的最大深度比较）+ 1`，是的，递归。但是和上面比起来，是自下而上。

求二叉树最大深度：

var maxDepth = function(root) { 
        if (root == null) { 
            return  0
        } else { 
            const leftMax =  maxDepth(root.left) 
            const rightMax = maxDepth(root.right)
            return Math.max(leftMax, rightMax) + 1
        }
    };

求总节点个数

var countNodes = function(root) { 
        if (root == null) { 
            return 0
        } else { 
            const m = countNodes(root.left) 
            const n = countNodes(root.right)
            return m + n + 1
        }
    };

求叶子节点个数：

var countLeafNodes = (root) => { 
        if (root == null) { 
            return 0
        }
        if (!root.left && !root.right) { 
            return 1
        }
        return countLeafNodes(root.left) + countLeafNodes(root.right)
    }