二叉树常见OJ题（笔记）

待我称王封你为后i 2023-10-13 12:52 45阅读 0赞

**目录**

前言

1. 根据二叉树创建字符串

2. 二叉树的层序遍历

3. 二叉树的层序遍历 II

4. 二叉树的最近公共祖先

5.二叉搜索树与双向链表

6.从前序与中序遍历序列构造二叉树

7. 二叉树的前序遍历非递归

8. 二叉树的中序遍历非递归

9. 二叉树的后序遍历非递归

--------------------

## 前言 ##

本篇总结了常见二叉树算法题，每个标题都有超链接，并给出AC代码。记得以后再刷几遍，容易忘记。

## 1. [根据二叉树创建字符串][Link 1] ##

## 2. [二叉树的层序遍历][Link 2] ##

## 3. [二叉树的层序遍历 II][II] ##

##    4. [二叉树的最近公共祖先][Link 3] ##

方法一：O(H\*N)

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool Find(TreeNode* sub,TreeNode* x)
        {
            if(sub==nullptr)
                return false;
            return sub == x
                ||Find(sub->left,x)
                ||Find(sub->right,x);
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            if(root==nullptr)
                return nullptr;
            
            if(root == p || root == q)
                return root;
            
            bool pInLeft,pInRight,qInLeft,qInRight;
            pInLeft = Find(root->left,p);
            pInRight = !pInLeft;
    
            qInLeft = Find(root->left,q);
            qInRight = !qInLeft;
    
            //1、一个在左一个在右，root就是最近公共祖先
            //2、都在左，递归去左子树找
            //3、都在右，递归去右子树找
            if((pInLeft&&qInRight)||(qInLeft&&pInRight))
            {
                return root;
            }
            else if(pInLeft&&qInLeft)
            {
                return lowestCommonAncestor(root->left,p,q);
            }
            else if(pInRight&&qInRight)
            {
                return lowestCommonAncestor(root->right,p,q);
            }
            else
            {
                //理论上不会走到这里
                return nullptr;
            }
        }
    };

方法二：O(N)

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>&path)
        {
            if(root==nullptr)
                return false;
            
            path.push(root);
            if(root == x)
                return true;
            
            if(FindPath(root->left,x,path))
                return true;
            
            if(FindPath(root->right,x,path))
                return true;
    
            path.pop();
            return false;
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*>pPath,qPath;
            FindPath(root,p,pPath);
            FindPath(root,q,qPath);
    
            //类似链表相交
            while(pPath.size()!=qPath.size())
            {
                if(pPath.size()>qPath.size())
                    pPath.pop();
                else
                    qPath.pop();
            }
    
            while(pPath.top()!=qPath.top())
            {
                pPath.pop();
                qPath.pop();
            }
            return pPath.top();
        }
    };

## 5.[二叉搜索树与双向链表][Link 4] ##

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
    	void InOrderConvert(TreeNode* cur,TreeNode*& prev)
    	{
    		if(cur == nullptr)
    			return;
    		
    		InOrderConvert(cur->left, prev);
    		cur->left = prev;
    		if(prev)
    			prev->right=cur;
    		
    		prev = cur;
    
    		InOrderConvert(cur->right, prev);
    	}
        TreeNode* Convert(TreeNode* pRootOfTree) {
            TreeNode* prev = nullptr;
    		InOrderConvert(pRootOfTree,prev);
    
    		TreeNode* head = pRootOfTree;
    		while(head&&head->left)
    		{
    			head=head->left;
    		}
    		return head;
        }
    };

## 6.[从前序与中序遍历序列构造二叉树][Link 5] ##

## 7. [二叉树的前序遍历][Link 6]非递归 ##

## 8. [二叉树的中序遍历][Link 7]非递归 ##

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
     //法一
    class Solution {
    public:
    
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> result;
            stack<TreeNode*> st;
            TreeNode*cur=root;
            while(cur!=nullptr||!st.empty())
            {
                if(cur!=nullptr)
                {
                    st.push(cur);
                    cur=cur->left;
                }
                else
                {
                    cur=st.top();
                    result.push_back(cur->val);
                    st.pop();
                    cur=cur->right;
                }
            }
            return result;
        }
    };
    //法二
    class Solution {
    public:
    
        vector<int> inorderTraversal(TreeNode* root) {
            stack<TreeNode*> st;
            vector<int> v;
            TreeNode* cur = root;
            while(cur || !st.empty())
            {
                //开始访问一棵树
                //1、左路节点入栈
                while(cur)
                {
                    st.push(cur);
                    cur = cur->left;
                }
                // 2、当左路节点从栈中出来，表示左子树已经访问过了，应该访问这个节点和它的右节点
                TreeNode*top = st.top();
                st.pop();
                v.push_back(top->val);
                cur = top->right;
            }
    
            return v;
        }
    };

## 9. [二叉树的后序遍历][Link 8]非递归 ##

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
     //法一
    class Solution {
    public:
    
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> result;
            stack<TreeNode*> st;
            if(root==NULL)return result;
            TreeNode*cur=NULL;
            TreeNode*pre=NULL;
            st.push(root);
            while(!st.empty())
            {
                cur=st.top();
                if((cur->left==NULL&&cur->right==NULL)||
                (pre!=NULL&&(pre==cur->left||pre==cur->right)))
                {
                    result.push_back(cur->val);
                    st.pop();
                    pre=cur;
                }
                else
                {
                    if(cur->right!=NULL)st.push(cur->right);
                    if(cur->left!=NULL)st.push(cur->left);
                }
            }
    
            return result;
        }
    };
    //法二
    class Solution {
    public:
    
        vector<int> postorderTraversal(TreeNode* root) {
            stack<TreeNode*> st;
            vector<int> v;
            TreeNode* cur = root;
            TreeNode* prev = nullptr;
            while(cur || !st.empty())
            {
                //开始访问一棵树
                //1、左路节点入栈
                while(cur)
                {
                    st.push(cur);
                    cur = cur->left;
                }
                // 2、当左路节点从栈中出来，表示左子树已经访问过了
                TreeNode*top = st.top();
    
                //栈顶节点右子树为空或者上一个访问节点是右子树的根，说明右子树已经访问过了，可以访问上一个节点的右数
                //否则 子问题访问top的右子树
                if(top->right == nullptr||top->right == prev)
                {
                    v.push_back(top->val);
                    prev = top;
                    cur = nullptr;
                    st.pop();
                }
                else{
                    cur = top->right;//子问题访问右子树
                }
            }
    
            return v;
        }
    };

[Link 1]: https://leetcode.cn/problems/construct-string-from-binary-tree/
[Link 2]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[II]: https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/
[Link 3]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[Link 4]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[Link 5]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[Link 6]: https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
[Link 7]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[Link 8]: https://leetcode.cn/problems/binary-tree-postorder-traversal/description/