Tree Property

Concepts

• balanced: clarify left height / right height. but left size - right size.
• completed: all nodes are full and leaf nodes are as left as possible.
• full
• depth
• height

不清楚没关系，记得clarify就行了。

Validate a BST

Solution I : carry subtree min-max range.

1. trapI: root.val >= max || root.val <= min, return false;

. no dup value allowed.

1. trapII: overflow, 初始值的选择。
   1. Method 1： use Long.MAX_VALUE instead of Integer.MAX_VALUE
   2. Method 2: use null to initialize. 因为leetcode有一个比较无语的testcase...

Solution II ： run inorder traversal and test if it's sorted.

Recover BST (two nodes swap by mistake)

Determine if a tree is perfect tree

Definition of perfect tree

• height of tree is k,
• all nodes have both left child and right child,
• count # of nodes : 2 ^ k.

Variant: count largest perfect tree in tree.

• [isPerfect, h]
• if left.isPerfect && right.isPerfect && l.h == r.h we could merge this two info into -> l.h = r.h

what we really care is only height of left subtree and right subtree

Complete Tree

Relationship with Perfect Tree(Full tree).

Observe from height property.

1. left height == right height || left height == right height + 1.
2. if height is equals:
   1. left is perfect, right is perfect
   2. left is perfect, right is complete

1. if height is not equal, left + 1 = right
   1. left is complete, right is complete.

Variant : count # of nodes in complete tree.

utilize complete tree property. assume left subtree height is lh, right subtree height is rh case (lh == rh) => left subtree is perfect case (lh == rh + 1) => right subtree is perfect