How does C++ define the height of a tree?

The knowledge points of this article "how C++ defines the height of a tree" are not quite understood by most people, so the editor summarizes the following, with detailed contents and clear steps, which can be used for reference. I hope you can get something after reading this article. Let's take a look at this "how C++ defines the height of a tree" article.

Algorithm:

This kind of problem is very simple, but it is one of the most basic operations of a tree, which is extended to determine whether a tree is a balanced binary tree.

The general practice is to calculate the height of the left and right subtrees of the binary tree + 1, and then take their maximum or minimum values.

Topic 1: definition of highly balanced binary tree

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / / A balanced binary tree, the absolute value of the height difference between the left and right subtrees is not more than 1 / / Note: if either node does not satisfy the balanced binary tree, then the tree is not a balanced binary tree. At this point, we can directly return flasefunc isBalanced (root * TreeNode) bool {if root = = nil {/ / nil, which means balanced binary tree return true} / / 1. The height difference between the left and right subtrees of the current node is 1 lH: = maxDepth (root.Left) rH: = maxDepth (root.Right) if abs (lH-rH) > 1 {return false} / / 2. Further determine whether the left subtree is a balanced binary tree if! isBalanced (root.Left) {return false} / / 3. Further determine whether the right subtree is a balanced binary tree return isBalanced (root.Right)} / / typical calculation of the height of the binary tree Maximum height of current left and right subtrees + 1func maxDepth (root * TreeNode) int {if root = = nil {return 0} return max (maxDepth (root.Left), maxDepth (root.Right)) + 1} func max (int b int) int {if a > b {return a} return b} func abs (an int) int {if a

< 0 { return -a } return a} 题目2:找出二叉树的最大深度 代码实现： /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func maxDepth(root *TreeNode) int { if root == nil { return 0 } left := maxDepth(root.Left) right := maxDepth(root.Right) if left >

Right {return left + 1} return right + 1} / * Recursive algorithm: the maximum height of the left and right subtrees + 1cm /

Topic 3: find out the minimum depth of the binary tree

Code implementation:

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode * * / func minDepth (root * TreeNode) int {if root = = nil {return 0} if root.Left = = nil & & root.Right = = nil {return 1} min: = int (^ uint (0) > > 1) if root.Left! = nil {/ / for a child's node To calculate the height of a node with children h: = minDepth (root.Left) if min > h {min = h}} if root.Right! = nil {h: = minDepth (root.Right) if min > h {min = h}} return min+1}

Topic 4 the maximum depth of an N-tree.

Code implementation:

/ * Definition for a Node. * type Node struct {* Val int * Children [] * Node *} * / func maxDepth (root * Node) int {if root = = nil {return 0} var hs [] int for _, n: = range root.Children {h: = maxDepth (n) hs = append (hs,h)} max: = 0 for _ H:=range hs {if h > max {max = h}} return max + 1} above is the content of this article on how C++ defines the height of a tree. I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please pay attention to the industry information channel.