二叉树非递归遍历

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

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

//非递归前序遍历二叉树
void preorder(TreeNode* root){
    stack<TreeNode> s;
    s.push(root);
    while(!s.empty()){
        TreeNode* t = s.top();
        s.pop();
        cout << t -> val << ' ';
        if(t -> right) s.push(t -> right);
        if(t -> left) s.push(t -> left);
    }
}

//非递归中序遍历二叉树
void inorder(TreeNode* root){
    stack<TreeNode> s;
    TreeNode* curr = root;
    while(curr || !s.empty()){
        //把当前结点的左节点全部入栈
        while(curr){
            s.push(curr);
            curr = curr -> left;
        }
        curr = s.top();
        s.pop();
        cour << curr -> val << ' ';
        curr = curr -> right;
    }
}

//非递归后序遍历二叉树
void postorder(TreeNode* root){
    stack<TreeNode> s1;
    stack<TreeNode> s2;
    TreeNode* p;
    s1.push(root);
    //逆后序遍历（根、右、左）序列逆序就得到后序遍历序列
    while(!s1.empty()){
        p = s1.top();
        s1.pop();
        s2.push(p);
        if(p -> left) s1.push(p -> left);
        if(p -> right) s2.push(p -> right);
    }

    while(!s2.empty()){
        p = s2.top();
        s2.pop();
        cout << p -> val << ' ';
    }
}

//层次遍历
void levelOrder(TreeNode* root){
    queue<TreeNode> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* t = q.front();
        q.pop();
        cout << t -> val << ' ';
        if(t -> left) q.push(t -> left);
        if(t -> right) q.push(t -> right);
    }
}

递归与非递归算法求树的高度

int height(TreeNode* root){
    if(!root) return 0;
    return max(height(root -> left),height(root -> right)) + 1;
}

int height2(TreeNode* root){
    if(!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int height = 0;
    while(!q.empty()){
        int n = q.size();//每一层有多少个结点
        while(n--){
            TreeNode *t = q.front();
            q.pop();
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        //遍历完一层结点高度 + 1;
        height++;
    }
    return height;
}

其他

//计算给定二叉树所有双分支结点的个数
int countDoubledot(TreeNode* root){
    if(!root) return 0;
    if(!root -> left && !root -> right) return countDoubledot(root -> left) + countDoubledot(root -> right) + 1;
    else return countDoubledot(root -> left) + countDoubledot(root -> right);
}
//计算给定二叉树所有双分支结点的个数(非递归做法)
void countDoubledot2(TreeNode* root){
    if(!root) return;
    if(root -> left && root -> right) res++;
    countDoubledot2(root -> left);
    countDoubledot2(root -> right);
}

//交换二叉树的所有左右结点
void swapLeft_and_right(TreeNode* root){
    if(!root) return;
    TreeNode* l;
    TreeNode* r;
    l = root -> left;
    r = root -> right;
    swap(l,r);
    swapLeft_and_right(root -> left);
    swapLeft_and_right(root -> right);
}
//求先序遍历序列中第 k(1≤k≤二叉树中结点个数)个结点的值。
int num = 0, k = 4, i = 0;
void preorder_k(TreeNode* root)
{
    i ++;
    if (i == k) num = root->val;
    if (root->left) dfs(root->left);
    if (root->right) dfs(root->right);
}

//对于树中每个元素值为x的结点，删去以它为根的子树
void deleteTree(TreeNode* root,char x){
    if(!root) return;
    if(root -> val == x) root = NULL;
    else{
        cout << root -> val << ' ';
        deleteTree(root -> left,x);
        deleteTree(root -> right,x);
    }

}
//树中两个结点的最低公共祖先
//（分别找出根节点到两个结点的路径，最后一个公共结点即为两个结点的最低公共祖先）
vector<TreeNode*> findPath(TreeNode* root,TreeNode* q){//找根结点到某结点的路径
    vector<TreeNode*> s;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while(cur || !s.empty()){
        while(cur){
            s.push_back(cur -> left);
            cur = cur -> left;
        }
        cur = s.back();
        if(cur -> right && cur -> right != pre)
            cur = cur -> right;
        else{
            s.pop_back();
            if(cur == p)
                return s;
            pre = cur;
            cur = NULL;
        }
    }
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    vector<TreeNode *> path1 = findPath(root, p);
    vector<TreeNode *> path2 = findPath(root, q);

    if (path1.size() > path2.size()) swap(path1, path2);
    for (int i = 0; i < path1.size(); i ++)
        if (path1[i] != path2[i])
            return path1[i - 1];
    return path1.back();
}
//递归版
TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q){
    if(!root) return NULL;
    if(root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor2(root -> left,p,q);
    TreeNode* right = lowestCommonAncestor2(root -> right,p,q);
    if(left && right) return root;
    if(left == NULL) return right;
    else return left;
}
//m是n的祖先，求m到n的路径
// 后序遍历查找路径m->n
bool postorder(TreeNode* root, TreeNode* n) 
{
    // 边界情况：空结点 -> 查找失败
    if (!root) 
        return false;

    // 递归遍历左右子树
    if (root == n || postorder(root->left, n) || postorder(root->right, n)) 
    {
        // 如果当前结点是目标结点n，或者在左右子树中找到了目标结点
        // 输出当前结点的值，并返回true
        cout << root->val << ' ';
        return true;
    }
}