二叉树应用题

标签：preorder right 应用题 inorder 遍历 二叉树 root left

1. 非递归先序

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> nums;
    stack<TreeNode*> s;
    while(root||!s.empty()){
        if(root){
            nums.push_back(root->val);//输出
            s.push(root);//入栈
            root = root->left;//往左走
        }
        else{
            root = s.top();s.pop();//出栈
            root = root->right;//往右走
        }
    }
    return nums;
}

2. 非递归中序

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> nums;
    stack<TreeNode*> s;
    while(root||!s.empty()){
        if(root){
            s.push(root);//入栈
            root = root->left;//往左走
        }
        else{
            root = s.top();s.pop();//出栈
            nums.push_back(root->val);//输出
            root = root->right;//往右走
        }
    }
    return nums;
}

3. 非递归后序

需要使用辅助指针进行判断

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> nums;
    stack<TreeNode*> s;
    TreeNode* r;//辅助判断指针，判断是从左子树出栈，还是右子树
    while(root||!s.empty()){
        if(root){
            s.push(root);//入栈
            root = root->left;//往左走
        }
        else{
            root = s.top();//得到栈顶
            if(root->right&&root->right!=r)//右子树存在，且不是刚出来
                root = root->right;//往右走
            else{
                s.pop();//出栈
                nums.push_back(root->val);//输出
                r = root;//记录最近访问
                root = NULL;//重置指针
            }
        }
    }
    return nums;
}

4. 自下而上、自右而左的层次遍历

使用队列和栈

void InvertLevel(TreeNode* root) {
    queue<TreeNode*> q;
    stack<int> s;
    q.push(root);
    while(!q.empty()){
        TreeNode* p = q.front();
        q.pop();
        s.push(p->val);
        if(p->left) q.push(p->left);
        if(p->right) q.push(p->right);
    }
    while(!s.empty()){
        cout<<s.top();//逆序输出
        s.pop();
    }
}

5. 非递归求高度（层次遍历）

6. 先序、中序构建二叉树

 TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) return nullptr;
        int inorder_root = index[preorder[preorder_left]];// 在中序遍历中定位根节点，这里使用哈希优化，也可以遍历中序序列找根节点
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_left]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

7. 判断完全二叉树

借助队列，遇到空节点时，查看其后是否有非空节点

8. 计算度为2的节点

//递归

9. 交换左右子树

//递归

10. 找先序遍历第k个值

//全局变量递归

11. 删除指定的子树

12. 找指定值节点的所有祖先

//非递归后序遍历，访问到指定节点时，栈中所有元素皆为祖先

13. 两节点最近公共祖先

//非递归后序遍历

14. 二叉树的宽度

//层次遍历

15. 满二叉树先序转后序

16. 链表串联叶子节点

//记录全局变量pre和首个叶子节点，以任一种方式递归遍历

17. 判断相似

//递归判断

18.

19. 求带权路径长度

//先序遍历，累积求路径长度，递归时更新传入深度

20. 输出中缀表达式

//中序遍历

标签：preorder,right,应用题,inorder,遍历,二叉树,root,left
From： https://www.cnblogs.com/929code/p/16611349.html