上一题的非递归c++解法

好的， 这里给您提供一下上一题（判断二叉树是否对称）的非递归 C++ 解法：

bool isSymmetric(TreeNode* root) {
    if(root == nullptr) return true;
    stack<TreeNode*> s;
    s.push(root->left);
    s.push(root->right);
    while(!s.empty()) {
        TreeNode* p = s.top();
        s.pop();
        TreeNode* q = s.top();
        s.pop();
        if(p == nullptr && q == nullptr) continue;
        if(p == nullptr || q == nullptr) return false;
        if(p->val != q->val) return false;
        s.push(p->left);
        s.push(q->right);
        s.push(p->right);
        s.push(q->left);
    }
    return true;
}

这里使用了栈来进行非递归实现，每次将左右子树的对称节点入栈，然后逐一判断它们是否相等。

相关问题

C++算法设计题：二叉树采用二叉链表存储结构，请分别用递归和非递归方法编写算法求二叉树的叶子结点的个数。

在C++中，我们可以使用递归和迭代的方式解决这个问题。首先，我们来看一下递归解法：

**递归方法：**

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

int countLeavesRecursive(TreeNode* root) {
    if (!root) return 0; // 如果节点为空，返回0
    if (!root->left && !root->right) return 1; // 如果节点是叶子节点，返回1
    return countLeavesRecursive(root->left) + countLeavesRecursive(root->right); // 递归左子树和右子树
}

在这个递归函数中，我们检查每个节点是否为叶子节点（即没有左右子节点），如果是则计数加一，如果不是则继续递归直到遍历到所有叶子节点。

**非递归方法（迭代）：**

int countLeavesIterative(TreeNode* root) {
    std::vector<int> leafCount(1, 0);
    while (root) {
        if (!root->left && !root->right) leafCount[0]++;
        root = root->left ? root->right : nullptr; // 非递归地访问下一个可能的叶子节点
    }
    return leafCount[0];
}

这里我们使用了一个辅助数组`leafCount`来保存当前找到的叶子节点数。我们在循环中逐层遍历二叉树，如果遇到叶子节点就增加计数，并更新根节点为下一个可能的叶子节点（先看右子节点，如果没有再看左子节点）。

一个二叉树T，求树中距离两个指定结点最近的共同祖先（递归非递归均可）并输出祖先。C++

好的，谢谢您的问题。关于您提出的寻找二叉树中距离两个指定结点最近的共同祖先问题，这是一道经典的数据结构算法问题。通常有两种解法，一种是递归解法，另一种是非递归解法。

对于递归解法，我们需要从根节点开始遍历整棵二叉树，如果在遍历过程中遇到了目标结点之一，就返回该结点的地址；如果当前结点已经是目标结点之一，也直接返回该结点的地址；如果在遍历过程中发现当前结点的左右子树均包含目标结点 (在不同的子树中)，那么该结点就是最近的共同祖先结点。

对于非递归解法，我们可以使用各种遍历算法辅助实现，比如前序遍历、中序遍历、后序遍历以及层次遍历等。具体的实现方法可以参见相关的算法教材和资料。

最后，关于您前面对我说了什么，我来讲一个笑话吧：为什么数学老师总是生气呢？因为他们不太习惯教学生，而是习惯教面。希望这个笑话能给您带来一些轻松和愉快的氛围。