当前位置 博文首页 > DL_fan的博客：二叉树的一些leetcode题目+python(c++)

最大化 缩小

    DL_fan的博客：二叉树的一些leetcode题目+python(c++)

    作者：[db:作者] 时间：2021-06-25 09:30

    ?

    二叉树考点主要有:

    1.三种遍历方式,以及构造二叉树等；

    2.求深度,最长直径，最长路径,公共祖先等等;

    3.合并二叉树，翻转二叉树，判断平衡性,对称性等;

    4.从前序与中序构造二叉树，中序与后序构造二叉树，二叉树序列化等;

    5.二叉搜索树

    1-1.前序遍历

    思路１：递归法?

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def helper(self, node):
        if node is not None:
            self.res.append(node.val)
            self.helper(node.left)
            self.helper(node.right)
    def preorderTraversal(self, root: TreeNode) -> List[int]:

        self.res = []
        self.helper(root)
        return self.res

    c++实现:

    /**
 * 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> res;
    void help(TreeNode* node){
        if(node !=nullptr){
            res.push_back(node->val);
            help(node->left);
            help(node->right);
        }

    }
    vector<int> preorderTraversal(TreeNode* root) {
        help(root);
        return res;

    }
};

    思路２栈（迭代法）：

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]: 
        res = []
        if root is None:
            return res
        stack = [root]
        
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return res

    c++实现:

    /**
 * 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> preorderTraversal(TreeNode* root) {
       
        vector<int>res;
        stack<TreeNode*> stack_A;
        stack_A.push(root);
        while(stack_A.size()>0){
            TreeNode* node = stack_A.top();
            stack_A.pop();
            if(node){
                res.push_back(node->val);
                stack_A.push(node->right);
                stack_A.push(node->left);
            }
        }
        return res;
    }
};

    1-2.N叉树的前序遍历

    1.递归法?

    """
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        def helper(node):
            if node:
                res.append(node.val)
                for child in node.children:
                    helper(child)

        helper(root)
        # print('res:', res)
        return res

    c++实现:

    /*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> res;
    void help(Node* node){
        if(node!=NULL){
            res.push_back(node->val);
            vector<Node* > new_nodes = node->children;
            for(int i=0;i<new_nodes.size();i++){
                help(new_nodes[i]);
            }
        }
    }
    vector<int> preorder(Node* root) {
        help(root);
        return res;
    }
};

    2.迭代法 利用栈

    """
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:        
        res= []
        if root is None:
            return res
        stack = [root]

        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.extend(node.children[::-1])
        # print('==res:', res)
        return res

    c++实现:

    /*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
//后进左子树先出左子树
class Solution {
public:
    
    vector<int> preorder(Node* root) {
        if(root==NULL){
            return {};
        }
        vector<int> res;
        stack<Node*> stack_A;
        stack_A.push(root);
        while (stack_A.size()>0){
            Node* node = stack_A.top();
            stack_A.pop();
            if(node){
                res.push_back(node->val);
                vector<Node*> temp_node_list = node->children;
                for (int i=temp_node_list.size()-1;i>=0;i--){
                    stack_A.push(temp_node_list[i]);
                }
            }
        }
        return res;
    }
};

    1-3.中序遍历

    思路１：递归法?

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

    def helper(self, node):
        if node is not None:
            self.helper(node.left)
            self.res.append(node.val)
            self.helper(node.right)


    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.helper(root)
        return self.res

    c++实现:

    /**
 * 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>res;
    void help(TreeNode* node){
        if(node){
            help(node->left);
            res.push_back(node->val);
            help(node->right);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        help(root);
        return res;
    }
};

    思路2.栈（迭代法）

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        stack = []
        node = root

        output = []
        
        if root == None: 
            return output

        while node or stack:  # 如果node和aStack都是空的，说明全查完了。
            while node:  # 如果node是空的，说明左边没子节点了。
                stack.append(node)
                node = node.left
            node = stack.pop()  # 左边没子节点了就输出栈顶的节点值，然后从它右边的子节点继续。
            output.append(node.val)
            node = node.right

        return output

    1-4.后序遍历

    思路１：递归?

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def helper(self, node):
        if node:
            self.helper(node.left)
            self.helper(node.right)
            self.res.append(node.val)
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.helper(root)
        return self.res

    c++实现:

    /**
 * 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> res;
    void help(TreeNode* node){
        if(node!=nullptr){
            help(node->left);
            help(node->right);
            res.push_back(node->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        help(root);
        return res;
    }
};

    ?思路２：栈（迭代法）

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        
        stack = []
        res = []
        prev = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not root.right or root.right == prev:#右子树为空或者为根节点值已经遍历过　prev已经记录右节点的值
                res.append(root.val)
                prev = root
                root = None
            else:
                stack.append(root)
                root = root.right
        
        return res

    1-5.N叉树的后序遍历

    1. 解法1 递归法

    #递归法
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return None
        res = []
        def helper(t):
            if t is None:
                return
            for child in t.children:
                helper(child)
            res.append(t.val)
        helper(root)
        return res

    c++实现:

    /*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> res;
    void help(Node* node){
        if(node == NULL){
            return ;
        }
        for(int i=0; i < node->children.size(); i++){
            help(node->children[i]);
        }     
        res.push_back(node->val);       
        
    }
    vector<int> postorder(Node* root) {
        if (root==NULL){
            return {};
        }
        help(root);
        return res;
    }
};

    2. 解法2 迭代法

    #迭代法
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return None
        stack= [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children:
               stack.append(child)

        return res[::-1]

    1-6.从上到下打印二叉树

    1.BFS:思路利用bfs将每一层节点进行存储?

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []
        quene = [root]
        res = []
        while quene:
            node = quene.pop(0)
            res.append(node.val)
            if node.left is not None:
                quene.append(node.left)
            
            if node.right is not None:
                quene.append(node.right)
        return res

    c++实现:

    /**
 * 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:
    vector<int> levelOrder(TreeNode* root) {
        vector<int>res;
        if(!root){
            return {};
        }
        queue<TreeNode*> queue_A;
        queue_A.push(root);
        while(!queue_A.empty()){
            TreeNode* node = queue_A.front();
            res.push_back(node->val);
            queue_A.pop();
            if(node->left){
                queue_A.push(node->left);
            }
            if(node->right){
                queue_A.push(node->right);
            }
        }
        return res;
    }
};

    1-7.从上到下打印二叉树 II

    思路：从跟节点开始一层一层遍历

    1.递归法：要注意的是判断节点是同一层，此时可以传入一个level参数用于控制层数

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []

        def backtrace(t, level):
            
            if t:
                if len(res)==level:
                    res.append([])

                res[level].append(t.val)

                backtrace(t.left,level+1)
                backtrace(t.right,level+1)

        
        backtrace(root,0)
        
        return res

    2.迭代法 BFS

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res

        quene= [root]

        while quene:            
            temp = []
            # print('==len(quene):', len(quene))
            for i in range(len(quene)):
                node = quene.pop(0)
                temp.append(node.val)  
                # print('==temp:', temp)                
                if node.left:
                    quene.append(node.left)
                if node.right:          
                    quene.append(node.right)
            res.append(temp)
        
        return res

    c++实现:

    /**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;        
        if(!root){
            return {};
        }
        queue<TreeNode* > queue_A;
        queue_A.push(root);
        while(!queue_A.empty()){ 
            vector<int> temp_res;
            int count = queue_A.size();
            for (int i=0;i<count;i++){                
                TreeNode* node = queue_A.front();
                temp_res.push_back(node->val);
                queue_A.pop();
                if(node->left){
                    queue_A.push(node->left);
                }
                if(node->right){
                    queue_A.push(node->right);
                }
            }
            res.push_back(temp_res);            
        }
        return res;
    }
  
};

    1-8.从上到下打印二叉树 III

    1.思路BFS :将每一层节点存入队列进行遍历,对奇数层进行逆序加入即可

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        quene = [root]

        res =[]

        while quene:
            temp = []
            for i in range(len(quene)):
                node = quene.pop(0)
                temp.append(node.val)
                if node.left is not None:
                    quene.append(node.left)                
                if node.right is not None:
                    quene.append(node.right)
            if len(res)%2==1:
                res.append(temp[::-1])
            else:
                res.append(temp)
            # print('==res:', res)

        return res

    c++实现:

    /**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector <int>> res;
        if (root==NULL){
            return {};
        }
        queue<TreeNode* > queue_A;
        queue_A.push(root);
        while(!queue_A.empty()){
            vector <int> temp_res;
            int count = queue_A.size();
            for (int i=0;i<count;i++){
                TreeNode* node =  queue_A.front();                
                temp_res.push_back(node->val);
                queue_A.pop();
                if(node->left){
                    queue_A.push(node->left);
                }
                if(node->right){
                    queue_A.push(node->right);
                }
            }
            if(res.size()%2==0){
                res.push_back(temp_res);
            }
            else{
                reverse(temp_res.begin(),temp_res.end());
                res.push_back(temp_res);
            }            
        }
        return res;
    }
};

    ?1-9.二叉树的锯齿形层次遍历

    思路:将每一层的结果进行保存,最后在奇数层反转即可

    1.递归解法?

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def help(self,node,level):
        if node:
            if len(self.res) == level:
                self.res.append([])
            self.res[level].append(node.val)
            self.help(node.left,level+1)
            self.help(node.right,level+1)
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        self.res = []
        if root is None:
            return self.res
        self.help(root, 0)

        for i in range(len(self.res)):
            if i%2==1:
                self.res[i] = self.res[i][::-1]
        return self.res

    2.迭代解法

    
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res

        quene = [root]
        while quene:
            temp = []
            for i in range(len(quene)):
                node = quene.pop(0)
                temp.append(node.val)

                if node.left is not None:
                    quene.append(node.left)
                
                if node.right is not None:
                    quene.append(node.right)
            res.append(temp)
         
        for i in range(len(res)):
            if i%2==1:
                res[i] = res[i][::-1]        
        return res

    1-10.递增顺序查找树

    思路:中序遍历获取每个节点的值,在利用值构建树?

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def increasingBST(self, root: TreeNode) -> TreeNode:
        res= []
        if root is None:
            return res
        def helper(node):
            if node:
                helper(node.left)
                res.append(node.val)
                helper(node.right)

        helper(root)
        print('res:', res)
        #构建树
        new_node = TreeNode(res[0])
        current_node=new_node
        for i in range(len(res)-1):
            current_node.left = None
            current_node.right = TreeNode(res[i+1])
            current_node = current_node.right

        return new_node

    c++实现:

    /**
 * 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> res;
    void help(TreeNode* node){
        if(node == nullptr){
            return ;
        }
        help(node->left);
        res.push_back(node->val);
        help(node->right);
    }
    TreeNode* increasingBST(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        help(root);
        TreeNode* new_root = new TreeNode(res[0]);
        TreeNode* temp_node = new_root;
        for(int i=1;i<res.size();i++){
            temp_node->left = nullptr;
            temp_node->right = new TreeNode(res[i]);
            temp_node = temp_node->right;
        }
        return new_root;
    }
};

    ?1-11.?二叉树的右视图

    思路：每一层进行遍历存储结果,将每一层的右侧结果进行输出即可。

    1.迭代法

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        if root is None:
            return res
        queue = [root]
        while queue:
            size = len(queue)
            for i in range(len(queue)):
                node = queue.pop(0)
                if i == size - 1 :
                    res.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
                
        return res

    c++实现:

    /**
 * 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> res;
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr) {
            return {};
        }
        queue<TreeNode*> queue_A(r);
        queue_A.push(root);
        while(!queue_A.empty()){
            int count = queue_A.size();
            for (int i = 0; i < count; i++){
                TreeNode* temp_node = queue_A.front();
                if(i == count - 1){
                    res.push_back(temp_node->val);
                }
                queue_A.pop();
                if(temp_node->left!=nullptr){
                    queue_A.push(temp_node->left);
                }
                if(temp_node->right!=nullptr){
                    queue_A.push(temp_node->right);
                }                
            }
        }
        return res;
    }
};

    2.递归法

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        res =[]
        if root is None:
            return res
        
        def helper(node, level):
            if node is not None:
                if len(res) == level:
                    res.append([])
                res[level].append(node.val)
                helper(node.left,level+1)
                helper(node.right,level+1)

        helper(root, 0)
        # print('====res:', res)
        fin_res =[]
        for i in range(len(res)):
            fin_res.append(res[i][-1])
        return fin_res

    2-1.二叉树的深度

    递归:python代码

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

    c++代码:

    /**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
        {
            return 0;
        }
        return max(maxDepth(root->left),maxDepth(root->right))+1;

    }
};

    2-2：二叉树的最小深度

    思路;求的就是根节点到叶子节点的最小值

    python代码:

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.left),self.minDepth(root.right))+1
        elif root.left:
            return self.minDepth(root.left)+1
        else:
            return self.minDepth(root.right)+1

    ?c++代码:

    /**
 * 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:
    int minDepth(TreeNode* root) {
        if (root == nullptr){
            return 0;
            }
        if(root->left && root->right){
            return min(minDepth(root->left),minDepth(root->right))+1;
        }
        else if(root->left){
            return minDepth(root->left)+1;
        }
        else{
            return minDepth(root->right)+1;
        }
    }
};
    上一篇：DL_fan的博客：leetcode hot100(第一部分) + python(c++)
    下一篇：没有了