当前位置：首页 > article >正文

leetCode 100. 相同的树和 leetCode 101. 对称二叉树和 110. 平衡二叉树和 199. 二叉树的右视图

article 2024/9/24 9:20:26

1.leetCode 100. 相同的树

C++代码：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr || q == nullptr) return p==q;
        return p->val == q->val && isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

Python代码：

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

2.leetCode 101. 对称二叉树
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

C++代码：

class Solution {
public:
    bool isSameTree(TreeNode* p,TreeNode* q) {
        if(p == nullptr || q == nullptr) return p==q;
        return p->val == q->val && isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        TreeNode* p = root->left;
        TreeNode* q = root->right;
        return isSameTree(p,q);
    }
};

Python代码：

class Solution:
    def isSameTree(self,p:Optional[TreeNode],q:Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q
        return p.val == q.val and self.isSameTree(p.left,q.right) and self.isSameTree(p.right,q.left)

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left,root.right)

3.leetCode 110.平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/description/

C++代码：

class Solution {
public:
    int getHeight(TreeNode* root) {
        if(root==nullptr) return 0;
        int LH = getHeight(root->left);
        if(LH == -1) return -1;
        int RH = getHeight(root->right);
        if(RH == -1 or abs(RH-LH) > 1) return -1;
        return max(LH,RH)+1;
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root)!=-1;
    }
};

Python代码：

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node):
            if node is None: 
                return 0
            LH = get_height(node.left)
            if LH == -1:
                return -1
            RH = get_height(node.right)
            if RH == -1 or abs(RH-LH) > 1:
                return -1
            return max(LH,RH)+1
        return get_height(root)!=-1

4.leetCode 199. 二叉树的右视图
https://leetcode.cn/problems/binary-tree-right-side-view/description/

C++代码：

class Solution {
public:
    vector<int> ans;
    void dfs(TreeNode* node,int depth) {
        if(node==nullptr) return;
        if(depth == ans.size()) ans.push_back(node->val);
        dfs(node->right,depth+1);
        dfs(node->left,depth+1);
    }
    vector<int> rightSideView(TreeNode* root) {
        dfs(root,0);
        return ans;
    }
};

Python代码：

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def f(node,depth):
            if node is None:
                return 
            if depth == len(ans):
                ans.append(node.val)
            f(node.right,depth+1)
            f(node.left,depth+1)
        f(root,0)
        return ans

参考和推荐文章、视频：

如何灵活运用递归？【基础算法精讲 10】_哔哩哔哩_bilibili

100. 相同的树 https://leetcode.cn/problems/same-tree/solutions/2015056/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-empk/

101. 对称二叉树 https://leetcode.cn/problems/symmetric-tree/solutions/2015063/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-6dq5/

110. 平衡二叉树 https://leetcode.cn/problems/balanced-binary-tree/solutions/2015068/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-c3wj/

199. 二叉树的右视图 https://leetcode.cn/problems/binary-tree-right-side-view/solutions/2015061/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-r1nc/

查看全文

http://www.kler.cn/news/148738.html