Leetcode刷题之二叉树篇（二）

二叉树篇

111. 二叉树的最小深度

• 思路1：二叉树的最小深度需分情况讨论：节点无左孩子，则为右子树深度加1；无右孩子，则为左子树深度加1；左右孩子都有，为左子树和右子树深度较小值加1

class Solution(object):
    def minDepth(self, root):
        if not root: return 0
        if not root.left: return self.minDepth(root.right) + 1
        if not root.right: return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left),self.minDepth(root.right)) + 1

55-I. 二叉树的深度

• 思路1：二叉树的深度为 左右子树深度的最大值+1

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

55-II. 平衡二叉树

• 思路1：从上到下 以先序遍历的方式 遍历每个节点，并计算 每个节点的左右子树深度，如果深度差超过1，则不为平衡二叉树

class Solution(object):
    def isBalanced(self, root):
        if not root: return True;
        d_left = self.dfs(root.left)
        d_right = self.dfs(root.right)
        if abs(d_left-d_right) > 1:  return False
        a = self.isBalanced(root.left)
        b = self.isBalanced(root.right)
        return a and b

    def dfs(self,root):
        if not root: return 0
        return max(self.dfs(root.left),self.dfs(root.right))+1

总结：求平衡二叉树，关键在于去求 子树的深度

543. 二叉树的直径

• 思路1：直径实际上是左右子树的深度和的最大值，写dfs去求子树深度，用成员变量self.ret去获取整个求子树深度过程中，所有子树直径的最大值

class Solution(object):
    def __init__(self):
        self.ret = 0

    def diameterOfBinaryTree(self, root):
        if not root: return 0
        self.dfs(root)
        return self.ret

    def dfs(self,root):
        if not root: return 0
        a = self.dfs(root.left) 
        b = self.dfs(root.right)
        self.ret = max(self.ret,a+b)
        return max(a,b) + 1

总结：求二叉树的直径，关键在于求二叉树的深度

100. 相同的树

• 思路1：先判断两棵树对应节点是否同时为None，在都不为None情况下再去判断对应节点的val是否一样

class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q: return True
        if (not p)^(not q): return False
        if p.val != q.val: return False
        a = self.isSameTree(p.left,q.left)
        b = self.isSameTree(p.right,q.right)
        return a and b

28. 对称的二叉树

• 思路1： 先判断左右子树对称节点是否同时为None，在都不为None情况下再去判断对称节点的val是否一样 **

class Solution(object):
    def isSymmetric(self, root):
        if not root: return True
        return self.dfs(root.left,root.right)

    def dfs(self,p,q):
        if not p and not q: return True
        if (not p)^(not q): return False
        if p.val!=q.val: return False
        a = self.dfs(p.left,q.right)
        b = self.dfs(p.right,q.left)
        return a and b

26. 树的子结构

• 思路1：判断B是A 或 是A左孩子 或是A右孩子的子结构？满足一个即可。判断子结构 先判断两棵树对应节点是否同时为None，在都不为None情况下再去判断对应节点的val是否一样

class Solution(object):
    def isSubStructure(self, A, B):
        if not A or not B: return False
        c = self.dfs(A,B)
        a = self.isSubStructure(A.left,B)
        b = self.isSubStructure(A.right,B)
        return a or b or c

    def dfs(self,A,B):
        if not B: return True
        if (not A)^(not B): return False
        if A.val!=B.val: return False
        a = self.dfs(A.left,B.left)
        b = self.dfs(A.right,B.right)
        return a and b

27. 二叉树的镜像

• 思路1：只需递归将 root节点的左右孩子指向交换即可

class Solution(object):
    def mirrorTree(self, root):
        if not root: return
        root.left,root.right = root.right,root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root 

617. 合并二叉树

• 思路1：判断两颗二叉树是否都为None，在都不为None情况下，新建root节点，其值为两颗树对应节点val的和

class Solution(object):
    def mergeTrees(self, root1, root2):
        if not root1 and not root2: return None
        if root1 and not root2: return root1
        if not root1 and root2: return root2
        if root1 and root2:
            root = TreeNode(0)
            root.val = root1.val + root2.val
        root.left = self.mergeTrees(root1.left,root2.left)
        root.right = self.mergeTrees(root1.right,root2.right)
        return root

222. 完全二叉树的节点个数

思路1：直接求二叉树节点个数 为左子树个数+右子树个数+根节点(为1)

思路2：计算完全二叉树的深度L，根据深度算出前L-1层的节点个数，然后采取后序遍历统计最后一层节点个数(后序遍历也要遍历所有元素，时间复杂度并没有降低)

思路3：先求树深度，对树进行计数下标标记，根节点从1开始，后续节点依次加1。然后对最后一层计数下标进行二分查找(判断该mid节点是否在二叉树中，根据位运算找到mid节点位置，判断mid节点是否位None来进行二分)，查找到最后一个节点的 计数下标时，即为完全二叉树节点个数

# 思路1
class Solution(object):
    def countNodes(self, root):
        if not root: return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1
# 思路2
class Solution(object):
    def __init__(self):
        self.cnt = 0

    def countNodes(self, root):
        if not root: return 0
        depth = self.depth(root)
        self.dfs(root,depth,1)
        return pow(2,depth-1)-1 + self.cnt

    def depth(self,root):
        if not root: return 0
        return self.depth(root.left) + 1

    def dfs(self,root,depth,k):
        if not root: return
        self.dfs(root.left,depth,k+1)
        self.dfs(root.right,depth,k+1)
        # 后序遍历
        if k==depth:
            self.cnt += 1
        else:
            return
# 思路3
class Solution(object):
    def countNodes(self, root):
        if not root: return 0
        level,node = 0,root
        while node.left: # 求深度
            level += 1
            node = node.left
        low = 1 << level
        high = (1 << (level + 1)) - 1;
        while low < high: # 二分法
            mid = (high - low + 1) // 2 + low # 根节点计数下标1，然后依次加1，mid代表最后一层 中间节点计数下标
            if self.exists(root, level, mid): # 判断中间下标节点  是否在树中(不在则为None，在则不为None)
                low = mid # 不为None，说明最终节点在mid右侧
            else:
                high = mid - 1
        return low # low为最后一个节点计数下标

    def exists(self,root,level,k):
        bits = 1 << (level - 1) # 最多循环level次,从root节点去 寻找与mid计数下标对应的节点
        node = root
        while bits > 0: # 这个很巧妙
            if not (bits & k): # 根据mid节点的 每一位来判断 在树的哪个子树
                node = node.left
            else:
                node = node.right
            bits >>= 1
        return node != None