共计 561 个字符,预计需要花费 2 分钟才能阅读完成。
二叉搜寻树
性质:
1. 对于 BST 的每一个节点 node, 左子树节点的值都比 node 的值要小,右子树的值都比 node 的值大
2. 对于 BST 的每一个节点 node, 它的左侧子树和右侧子树都是 BST。
从算法题的角度来看 BST,除了它的定义,还有一个重要的性质:BST 的中序遍历后果是有序的
void traverse(TreeNode root){if(root==null){return;}
traverse(root.left);
// 中序遍历代码地位
print(root.val);
traverse(root.right);
}
寻找第K小的元素 \
思考每个根节点须要干什么,节点须要遍历本人时就将 rank 值加1,代表遍历到了第 rank 小的节点
int res=0;
int rank=0;
int kthSmallest(TreeNode root,int k){traverse(root,k);
return res;
}
二叉搜寻树转换为累加树
节点须要将本人的值更新为 res,res 代表以后从大到小的节点值的和
public void traverse(TreeNode root){if(root==null){return;}
traverse(root.right);
res+=root.val;
root.val=res;
traverse(root.left);
}
正文完