算法：树
2019-04-11 本文已影响0人
Zack_H
- 树的常用算法
先序、中序、后序递归算法：
void inOrder(TreeNode root){
// 先序遍历递归算法
if (root != null){
System.out.print(root.val);
inOrder(root.left);
inOrder(root.right);
}
}
层序递归算法：
参考：https://blog.csdn.net/qq_38181018/article/details/79855540
void BTreeLevelOrder(BTNode* root)
{
if (root == NULL) return;
int dep = BTreeDepth(root); // 先递归算最大深度
for (int i = 1; i <= dep; i++)
_BTreeLevelOrder(root, i);
}
void _BTreeLevelOrder(BTNode* root, size_t i)
{
if (root == NULL || i == 0) return;
if (i == 1)
{
printf("%d ", root->_data);
return;
}
_BTreeLevelOrder(root->_left, i - 1);
_BTreeLevelOrder(root->_right, i - 1);
}
层序非递归算法：
void BTreeLevelOrderNonR(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (QueueEmpty(&q) != 0)
{
BTNode* front = QueueFront(&q);
printf("%d ", front->_data);
QueuePop(&q);
if (front->_left)
QueuePush(&q, front->_left);
if (front->_right)
QueuePush(&q, front->_right);
}
}
中序非递归算法：
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack();
List<Integer> res = new ArrayList();
TreeNode n = root;
while (n != null || !s.isEmpty()){
if (n != null){
s.push(n);
n = n.left;
}else{ // 当前一结点为null时，则可以输出当前栈顶结点
n = s.pop();
res.add(n.val);
n = n.right;
}
}
return res;
}
- 104 二叉树的最大深度
非递归算法，同时可以计算各结点对应的深度
public int maxDepth(TreeNode root) {
Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root != null) {
stack.add(new Pair(root, 1));
}
int depth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.poll();
root = current.getKey();
int current_depth = current.getValue();
if (root != null) {
depth = Math.max(depth, current_depth);
stack.add(new Pair(root.left, current_depth + 1));
stack.add(new Pair(root.right, current_depth + 1));
}
}
return depth;
}
- 98 验证二叉搜索树
递归算法：先验证左子树，确定结点值是否升序增加，再验证右子树
double last = -Double.MAX_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
if (isValidBST(root.left)) {
if (last < root.val) { // 结点值应当从小到大
last = root.val;
return isValidBST(root.right);
}
}
return false;
}
- 101 对称二叉树
递归算法：转化为求两棵树是否镜像对称
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
非递归算法：使用队列，把应该相等的两值先后入队，再一起出队比较
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
queue.add(root);
while (!queue.isEmpty()){
TreeNode n1 = queue.poll();
TreeNode n2 = queue.poll();
if (n1 == null && n2 == null) continue;
if (n1 == null || n2 == null) return false;
if (n1.val != n2.val) return false;
queue.add(n1.left); //最初时会重复结点，但后续就不重复了
queue.add(n2.right);
queue.add(n1.right);
queue.add(n2.left);
}
return true;
}
- 102 二叉树的层次遍历
递归算法：
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
pre(root, 0, ans);
return ans;
}
void pre(TreeNode *root, int depth, vector<vector<int>> &ans) {
if (!root) return ;
if (depth >= ans.size()) // depth是从0开始的
ans.push_back(vector<int> {});
ans[depth].push_back(root->val);
pre(root->left, depth + 1, ans);
pre(root->right, depth + 1, ans);
}
非递归算法：
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null)
return new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> list = new ArrayList<Integer>();
while(count > 0){ // 直接存储一行上的所有结点
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
count--;
}
res.add(list);
}
return res;
}
- 108 将有序数组转换为二叉搜索树
区间分治的方法：使用左闭右闭
参考：https://blog.csdn.net/FlushHip/article/details/82319086
mid = s + (e-s)/2 //防止溢出；保证中点上下界统一。也可以使用>>1
递归算法：
public TreeNode sortedArrayToBST(int[] nums) {
// 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
return nums == null ? null : buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int s, int r) {
if (s > r) {
return null;
}
int m = s + (r - s) / 2;
TreeNode root = new TreeNode(nums[m]);
root.left = buildTree(nums, s, m - 1);
root.right = buildTree(nums, m + 1, r);
return root;
}
- 103 二叉树的锯齿形层次遍历
同102 二叉树的层次遍历，然后再反转需要逆序的层 - 105 从前序与中序遍历序列构造二叉树
递归算法：先找到前序数组首项在中序数组的索引，然后分治构造子树。其中，可通过计算中序左右子数组的长度得到对应子前序数组。
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeRecurrent(preorder,inorder,0,inorder.length-1);
}
private TreeNode buildTreeRecurrent(int[] preorder, int[] inorder, int s, int e){
if (s>e)
return null;
if (s==e)
return new TreeNode(inorder[s]);
int rootInd = -1;
int reI = 0;
for (int i = 0;i<preorder.length;i++){ // 另一种方法：通过计算中序左数组长度得到对应前序数组范围，右数组同理。如此可以极大缩短运行时间
for (int j=s;j<=e;j++){
if (preorder[i] == inorder[j]){
rootInd = j;
reI = i;
break;
}
}
if (rootInd != -1)
break;
}
for (int i=reI;i<preorder.length-1;i++){
preorder[i] = preorder[i+1];
}
TreeNode node = new TreeNode(inorder[rootInd]);
node.left = buildTreeRecurrent(preorder, inorder, s, rootInd-1);
node.right = buildTreeRecurrent(preorder, inorder, rootInd+1, e);
return node;
}
116 填充每个节点的下一个右侧节点指针
递归算法：
void connect(TreeLinkNode *root) {
if (root == NULL || root->left == NULL)
return;
root->left->next = root->right;
if (root->next) // 递归的子操作是：结点的左孩子next指右孩子，右孩子指其next结点的左孩子
root->right->next = root->next->left;
connect(root->left);
connect(root->right);
}
非递归算法（树的双指针）：pre记录一层的第一个结点，cur按层序遍历，依次添加next值
public Node connect(Node root) {
if (root == null)
return root;
Node pre = root;
Node cur = null;
while (pre.left != null){
cur = pre;
while (cur != null){
cur.left.next = cur.right;
if (cur.next != null)
cur.right.next = cur.next.left; //针对每个结点的子操作如上的递归算法
cur = cur.next; // 每层自左向右
}
pre = pre.left;
}
return root;
}
- 230 二叉搜索树中第K小的元素
非递归算法：非递归中序遍历二叉树，直接找到第k个值
进阶：应该可以用OST(有序统计树）的思想，改变数据结构，在插入删除时一直维护结点的序号
