Leetcode——二叉树

快来打我* 2023-01-09 15:34 123阅读 0赞

[相同的树][Link 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            if not p and not q :return True
            if not p or not q : return False
            if p.val != q.val:return False
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[删除二叉搜索树中的节点][Link 2]

方法：递归  
这里有三种可能的情况：

1.  要删除的节点为**叶子节点**，可以直接删除。
2.  删除的几点**不是叶子节点且拥有右节点**，则该节点可以由该节点的后继节点进行替代，该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。
3.  要删除的节点**不是叶子节点**，**且没有右节点但是有左节点**。这意味着它的后继节点在它的上面，但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。

算法：

*  如果 key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
 *  如果 key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
 *  如果 key == root.val，则该节点就是我们要删除的节点，则：
 *  如果该节点是叶子节点，则直接删除它：root = null。
 *  如果该节点不是叶子节点且有右节点，则用它的后继节点的值替代 root.val = successor.val，然后删除后继节点。
 *  如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代 root.val = predecessor.val，然后删除前驱节点。
 *  返回 root。

class Solution:
        def successor(self, root):
            root = root.right
            while root.left:
                root = root.left
            return root.val
        
        def predecessor(self, root):
            root = root.left
            while root.right:
                root = root.right
            return root.val
            
        def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
            if not root:
                return None
            if key > root.val:
                root.right = self.deleteNode(root.right, key)
            elif key < root.val:
                root.left = self.deleteNode(root.left, key)
            else:
                if not (root.left or root.right):
                    root = None
                elif root.right:
                    root.val = self.successor(root)
                    root.right = self.deleteNode(root.right, root.val)
                else:
                    root.val = self.predecessor(root)
                    root.left = self.deleteNode(root.left, root.val)                 
            return root

![d82aa567dd7d504c93fb9997aa78a720.png][]

[Link 1]: https://leetcode-cn.com/problems/same-tree/
[Link 2]: https://leetcode-cn.com/problems/delete-node-in-a-bst/
[d82aa567dd7d504c93fb9997aa78a720.png]: /images/20221119/bf4e8097c94940759812eb0bcd45aebd.png