求解二叉树问题从递归着手

Problem 1

计算二叉树的形状
卡特兰树的经典应用
即给定n个节点，计算有多少个不同形状的二叉树，考虑当只有一个节点或者没有节点时树只有1个形状，当有多个节点时，给根节点分配一个，左右两边各有不同的分法，以此类推，采用递归求解，符合卡特兰数的表达，代码如下：

def count(n):
    # root : 1
    # left : k [0,n-1]
    # right : n - 1 - k
 
    if n == 0:
        return 1
    sum = 0
    for k in range(n):
        sum += count(k) * count(n-1-k)
    return sum

Problem 2

计算二叉树的最近祖先
Leetcode 236
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

image.png

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if p==root or q==root or root==None:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left==None and right!=None:
            return right
        if left!=None and right==None:
            return left
        if left==None and right==None:
            return None
        return root

Problem 3验证二叉树是否为二叉查找树

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

image.png

思路：
鄙人刚开始的想法是递归判断节点的左子树的值比根节点小，右子树的值比根节点大，如此可以保证局部的子树是二叉查找树，但并不能保证全局的结果，于是乎，转用其他方法，二叉查找树的中序遍历结果必然是有序的，如此得到了AC，代码如下：

 ret=[]
        stack=[]
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                temNode = stack.pop()
                ret.append(temNode.val)
                root = temNode.right
        return all([ret[i] < ret[i+1] for i in range(len(ret)-1)])

补充二叉树的前序、中序、后序遍历是基础中的基础，需要熟练掌握。

Probelm4二叉树的子树和子结构判断

树的子结构判断

def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
            if A==None or B==None:
                return False
            elif A.val==B.val:
                return  A.val==B.val or self.isSubStructure(A.left,B.left) or self.isSubStructure(A.right,B.right)
            else:
                return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

树的子树判断
如果两个数的根节点相同，判断两个树是否相等，否则判断左右子树是否是子树的关系。

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def isEqual(S,T): 
            if not S and not T:  
                return True  
            if S and T:  
                if S.val!=T.val:  
                    return False  
                return isEqual(S.left,T.left) and isEqual(S.right,T.right)  
            else:  
                return False

        if not root:
                return False
        return isEqual(root,subRoot) or self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)