树中节点的距离
树中两个节点的距离定义为连接两个节点的边的长度和，假设边长度都为1，则为连接的边的条数。例如
1
/ \
2 3
/ \
4 5
中4，5距离为2，以为 4 - 2 -5，中间有两条边。
- 求树中指定两个节点的距离
- 求树中任意两个节点的最大距离
/**
* Diameter of Binary Tree
* @param root
* @return
*<p>Description: </p>
*/
public int diameter(TreeNode root){
maxDepth(root);
return max;
}
public int maxDepth(TreeNode root){
if(root==null){
return 0;
}
int left=maxDepth(root.left);
int right=maxDepth(root.right);
max=Math.max(max, left+right);
return Math.max(left, right)+1;
}
遍历
- 深度优先、广度优先
- 前、中、后序遍历一棵树
- 求指定节点的中序遍历顺序的下一个节点(https://blog.csdn.net/qazwyc/article/details/70478222)
class Holder {
Node target;
boolean found = false;
}
private void findNextByInOrderTraversal(Node current, int value, Holder holder) {
if (holder.found) {
return;
}
if (current == null) {
return;
}
findByInOrderTraversal(current.left, value, holder);
if (holder.target != null) {
holder.target = current;
holder.found = true;
return;
}
if (current.value == value) {
holder.target = current;
}
findByInOrderTraversal(current.right, value, holder);
}
二叉搜索树
二叉搜索树中根节点大于等于左子树所有节点，小于等于右子树所有节点。
- 给定一组乱序的元素，创建一颗二叉搜索树；判断二叉树是否为平衡二叉树（左右子树高度差小于等于1）；转换一个二叉树为平衡二叉树
- 给定排序的元素，构造平衡二叉搜索树
- 查找一个指定元素；查找大小为第K个的元素
- 查找最近公共祖先（lowest common ancestor (LCA)）
