平衡二叉树非递归实现

平衡二叉树（AVL树）是一种自平衡的二叉搜索树，它的左子树和右子树的高度差不超过1。非递归实现平衡二叉树可以通过迭代的方式进行操作。以下是平衡二叉树的非递归实现的一般步骤：

1. 定义一个栈，用于存储待处理的节点。
2. 从根节点开始，将根节点入栈。
3. 循环执行以下步骤，直到栈为空：
- 弹出栈顶节点，记为当前节点。
- 计算当前节点的平衡因子（左子树高度减去右子树高度）。
- 如果平衡因子大于1或小于-1，表示当前节点不平衡，需要进行旋转操作来保持平衡。
- 如果当前节点有左子节点，则将左子节点入栈。
- 如果当前节点有右子节点，则将右子节点入栈。

在进行旋转操作时，可以使用左旋和右旋两种操作来调整树的结构。左旋是指将当前节点的右子节点提升为新的根节点，同时将新根节点的左子节点作为当前节点的右子节点。右旋是指将当前节点的左子节点提升为新的根节点，同时将新根节点的右子节点作为当前节点的左子节点。

相关问题

平衡二叉树非递归实现c++代码

平衡二叉树（AVL树）是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1。下面是一个非递归实现的平衡二叉树的C++代码示例：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    int height;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), height(1), left(NULL), right(NULL) {}
};

int getHeight(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

int getBalanceFactor(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

TreeNode* rotateLeft(TreeNode* node) {
    TreeNode* newRoot = node->right;
    node->right = newRoot->left;
    newRoot->left = node;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}

TreeNode* rotateRight(TreeNode* node) {
    TreeNode* newRoot = node->left;
    node->left = newRoot->right;
    newRoot->right = node;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;
    return newRoot;
}

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    } else {
        return root;  // 不允许插入重复的节点
    }
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    int balanceFactor = getBalanceFactor(root);
    if (balanceFactor > 1 && val < root->left->val) {
        return rotateRight(root);
    }
    if (balanceFactor < -1 && val > root->right->val) {
        return rotateLeft(root);
    }
    if (balanceFactor > 1 && val > root->left->val) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    if (balanceFactor < -1 && val < root->right->val) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }
    return root;
}

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* curr = root;
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

int main() {
    TreeNode* root = NULL;
    int arr[] = {3, 2, 4, 5, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    cout << "Inorder traversal of the AVL tree: ";
    inorderTraversal(root);
    return 0;
}

这段代码实现了平衡二叉树的插入操作，并通过中序遍历打印出了平衡后的树节点值。你可以根据需要进行修改和扩展。

java非递归平衡二叉树

在Java中，可以使用非递归的方法来判断一个二叉树是否是平衡二叉树。一种常用的方法是使用栈来进行遍历。具体的实现如下所示：

import java.util.Stack;

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            
            int leftDepth = depth(cur.left);
            int rightDepth = depth(cur.right);
            
            if (Math.abs(leftDepth - rightDepth) > 1) {
                return false;
            }
            
            if (cur.right != null) {
                stack.push(cur.right);
            }
            
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        
        return true;
    }
    
    private int depth(TreeNode node) {
        if (node == null) return 0;
        
        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}