算法:计算二叉树的高度
算法 About 2,781 wordsJava 实现
public class TreeHeight {
public static void main(String[] args) {
TreeHeight tree = new TreeHeight();
Node node1 = new Node(3);
Node node2 = new Node(9);
Node node3 = new Node(20);
Node node4 = new Node(15);
Node node5 = new Node(7);
/*tree.add(node1);
tree.add(node2);
tree.add(node3);
tree.add(node4);
tree.add(node5);*/
// System.out.println(tree.root.id);
// System.out.println(tree.height(tree.root));
tree.root = node1;
node1.left = node2;
node1.right = node3;
node3.left = node4;
node3.right = node5;
System.out.println(tree.height(tree.root));
}
public Node root;
public int height(Node node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public void add(Node node) {
root = add(root, node);
}
private Node add(Node root, Node node) {
if (root == null) {
return node;
}
if (root.id > node.id) {
root.left = add(root.left, node);
} else {
root.right = add(root.right, node);
}
return root;
}
private static class Node {
public int id;
public Node left;
public Node right;
public Node(int id) {
this.id = id;
}
}
}
Golang 实现
定义树和节点
type AVLTree struct {
root *AVLNode
}
type AVLNode struct {
id int
left *AVLNode
right *AVLNode
}
当前节点的高度
递归结算,并注意自身节点高度为1
,递归一次累加1
。
// Height 以当前节点为根节点的树的高度
func (node *AVLNode) Height() int {
var leftHeight int
if node.left == nil {
leftHeight = 0
} else {
leftHeight = node.left.Height()
}
var rightHeight int
if node.right == nil {
rightHeight = 0
} else {
rightHeight = node.right.Height()
}
if leftHeight > rightHeight {
return leftHeight + 1
} else {
return rightHeight + 1
}
}
当前节点左子树的高度
func (node *AVLNode) leftHeight() int {
if node.left == nil {
return 0
}
return node.left.Height()
}
当前节点右子树的高度
func (node *AVLNode) rightHeight() int {
if node.right == nil {
return 0
}
return node.right.Height()
}
树的高度
func (tree *AVLTree) Height() int {
return tree.root.Height()
}
树的左子树高度
func (tree *AVLTree) leftHeight() int {
if tree.root.left == nil {
return 0
}
return tree.root.leftHeight()
}
树的右子树高度
func (tree *AVLTree) rightHeight() int {
if tree.root.right == nil {
return 0
}
return tree.root.rightHeight()
}
Views: 2,339 · Posted: 2021-02-17
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...