二叉树--Leetcode(python)

树的遍历

在这里插入图片描述
前序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

层次遍历：1 2 3 4 5 6 7 8

二叉树的前序遍历

递归：

# 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 preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        
        res = [root.val]
        res += self.preorderTraversal(root.left)
        res += self.preorderTraversal(root.right)
        
        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]:
        if not root:
            return []
        
        stack, res = [], []
        cur = root
        while stack or cur:
            if cur:
                res.append(cur.val)
                stack.append(cur.right)
                cur = cur.left
            else:
                cur = stack.pop()
                
        return res

中序遍历二叉树

递归：

# 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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        
        res = []
        res += self.inorderTraversal(root.left)
        res += [root.val]
        res += self.inorderTraversal(root.right)
                
        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 inorderTraversal(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        
        stack, res = [], []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
                
        return res

二叉树的后序遍历

递归：

# 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 postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        
        res = []
        res += self.postorderTraversal(root.left)
        res += self.postorderTraversal(root.right)
        res += [root.val]
        
        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]:
        if not root:
            return []
        
        res, stack = [], []
        cur = root
        while stack or cur:
            if cur:
                res.append(cur.val)
                stack.append(cur.left)
                cur = cur.right
            else:
                cur = stack.pop()
                
        return res[::-1]

二叉树的层次遍历

队列迭代：

# 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 not root:
            return []
        
        queue = [(root, 0)]
        res = [[]]
        while queue:
            cur, level = queue.pop(0)
            res[level].append(cur.val)
            if cur.left:
                queue.append((cur.left, level+1))
            if cur.right:
                queue.append((cur.right, level+1))
            if len(res) <= level + 1:
                res.append([])
            
        return res[:-1]

按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解法
就是正常的层次遍历，记录层数，在奇数层的时候改变插入位置就可以了。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        q = [(pRoot, 0)]
        while q:
            cur, d = q.pop(0)
            if d >= len(res):
                res.append([])
            if d % 2 == 0:
                res[-1].append(cur.val)
            else:
                res[-1].insert(0, cur.val)
                
            if cur.left:
                q.append((cur.left, d + 1))
            if cur.right:
                q.append((cur.right, d + 1))
                
        return res

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

	1
   / \
  2   3
     / \
    4   5

序列化为 “[1,2,3,null,null,4,5]”
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解法
序列化：就是层次遍历，用一个堆存储一下先进先出的节点
反序列化：其实就是反过程

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        res = [str(root.val)]
        nodes = [root]
        while nodes:
            cur = nodes.pop(0)
            if cur.left:
                res.append(str(cur.left.val))
                nodes.append(cur.left)
            else:
                res.append('#')
            if cur.right:
                res.append(str(cur.right.val))
                nodes.append(cur.right)
            else:
                res.append('#')
        
        return ' '.join(res)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        if not data:
            return None
        res = data.split()
        ll = len(res)
        nodes = []
        root = TreeNode(res[0])
        nodes.append(root)
        
        i = 1
        while i < ll:
            cur = nodes.pop(0)
            if res[i] == '#':
                cur.left = None
            else:
                cur.left = TreeNode(res[i])
                nodes.append(cur.left)
                
            i += 1
            if res[i] == '#':
                cur.right = None
            else:
                cur.right = TreeNode(res[i])
                nodes.append(cur.right)
                
            i += 1
            
        return root
        
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

解法

  • 自顶向下的递归：每次传入的参数是当前层的深度，在叶子节点处更新结果
  • 自底向上的递归：每次都分成左右节点的子任务，即左右节点的最大深度+1就是当前节点为根时的最大深度。
  • 非递归方法：循环的思路是这样子的。和打印二叉树一样，将二叉树的每一层都存在数组里。然后看遍历完以后数组中有多少层，那就是二叉树的深度。

解法一：

# 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 __init__(self):
        self.res = 0

    def maxDepth(self, root, depth=1):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if not root.left and not root.right:
            self.res = max(self.res, depth)
                
        self.maxDepth(root.left, depth + 1)
        self.maxDepth(root.right, depth + 1)
            
        return self.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 maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        
        return max(left, right) + 1

解法三：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 层次遍历
    def levelOrder(self, root):
        # 存储最后层次遍历的结果
        count = 0   # 如果根节点为空，则返回空列表
        if root is None:
            return count
        q = []   # 模拟一个队列储存节点
        q.append(root)   # 首先将根节点入队
        while len(q) != 0:  # 列表为空时，循环终止
            length = len(q)    # 记录同层节点的个数
            count += 1  # 统计层数
            for i in range(length):
                r = q.pop(0)   # 将同层节点依次出队
                if r.left is not None:
                    q.append(r.left)   # 非空左孩子入队
                if r.right is not None:
                    q.append(r.right)   # 非空右孩子入队
                
        return count
 
    def TreeDepth(self, pRoot):
        # 使用层次遍历 当树为空直接返回0
        if pRoot is None:
            return 0
        count = self.levelOrder(pRoot)
        return count

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:


给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

解法

  • 用两个递归算法就可以了。一个是得到节点的高度；一个判断当前节点是否平衡
  • 求深度那个递归需要调用好几次，而且其中可能会有些重复计算。所以可以用自底向上的方法来求，利用后序遍历：左子树、右子树、根节点,可以先递归到叶子节点，然后在回溯的过程中来判断是否满足条件。
# 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 depth(self, root):
        if not root:
            return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1
    
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        if abs(self.depth(root.left) - self.depth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

方法2：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def depth(self, root):
        if not root:
            return 0
        l = self.depth(root.left)
        if l == -1:
            return -1
        r = self.depth(root.right)
        if r == -1:
            return -1
        if abs(l - r) > 1:
            return -1
        return max(l, r) + 1
        
        
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        if self.depth(pRoot) == -1:
            return False
        return True

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解法
把左右子树看成独立的两个树，然后分别判断左树右节点和右树左节点，右树左节点和左树右节点是否相等。
（不能用前中后序遍历的方式判断两个子树是否镜像，因为总会有相同的表示方法）

# 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 isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        return self.judge(root.left, root.right)
    
    def judge(self, p, q):
        if not p and not q:
            return True
        
        if p and q and q.val == p.val:
            a = self.judge(p.left, q.right)
            b = self.judge(p.right, q.left)
            
            return a and b
        else:
            return False

二叉树的镜像

题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
在这里插入图片描述
解法
就直接递归的交换处理左右子树就可以

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if root == None:
            return root
        
        root.left, root.right = root.right, root.left
        root.left = self.Mirror(root.left)
        root.right = self.Mirror(root.right)
        
        return root

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解法
题意：试图找到一条节点和为Num的路径
可以分解为子任务：左右子节点作为根节点时，试图找到节点和为num-val的路径。
临界条件：root=None的时候永远都是False；只有在左右都没有子节点的才是叶子节点，叶子节点处判断是否存在这样的路径。

# 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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right:
            if sum == root.val:
                return True
            else:
                return False
        
        if self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val):
            return True
        return False

二叉树中和为某一值的路径（路径总和II)

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解法
显然是使用递归的方法。注意要判断叶子节点。关键是在递归上面加上两个全局变量存储结果。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.path = []
        self.res = []
        
    def dfs(self, root, expectNumber):
        self.path.append(root.val)
        if root.val == expectNumber and not root.left and not root.right:
            self.res.append(self.path)
        
        if root.left:
            self.dfs(root.left, expectNumber - root.val)
        if root.right:
            self.dfs(root.right, expectNumber - root.val)
        
        self.path = self.path[:-1]
        
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return self.path
        self.dfs(root, expectNumber)
        
        return self.res

路径总和III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

解法

  • 先计算包含根节点的情况，在递归求解不包含根节点的左右子树，统计相加即可。
  • 计算树的前缀和：因为这个题求的是一段路径的和是否满足目标，可以考虑用哈希表记录下路径的前缀和，如果当前节点a前缀和为cur，如果找到一个点b前缀和为cur-sum，则[a,b]之间就是所要求的路径，也即存在了。进一步，由于题目求的是出现的次数，可以使用HashMap记录cur-sum出现的次数，结果就是满足条件的路径的数量。

解法一：

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
    
    def path(self, root, sum):
        if not root:
            return 0
        res = 0
        if root.val == sum:
            res += 1
        res += self.path(root.left, sum - root.val)
        res += self.path(root.right, sum - root.val)
        return res

解法二：

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.ans = 0
        prefix_sum = defaultdict(int)
        prefix_sum[0] = 1
        def dfs(node: TreeNode, total: int):
            if node is None:
                return
            total += node.val
            self.ans += prefix_sum[total-sum]
            prefix_sum[total] += 1
            dfs(node.left, total)
            dfs(node.right, total)
            prefix_sum[total] -= 1
        dfs(root, 0)
        return self.ans

二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解法
首先理解题意：最大路径和是指节点和最大的一条路径的和。想到用递归，那么转移方程是什么呢？
对于某个节点来说，有两种情况，要么被算入路径中，要么没有，而且只能通过它是root的情况来判断，即某节点作为root算入路径中。
如果该节点是最大路径和的root，那么就是这个节点的值+左右子树的最大路径和（若为负数，就设为0，即不算该子树）。
注意递归的返回值应该是左右子树较大的那个子树加上当前节点的值，因为往父节点回溯的话，最大路径就不能同时包含左右两个子树。

# 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 __init__(self):
        self.res = float("-inf")
        
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        
        self.getmax(root)
        
        return self.res
    
    def getmax(self, root):
        if not root:
            return 0
        left = max(0, self.getmax(root.left))
        right = max(0, self.getmax(root.right))
        self.res = max(self.res, left + right + root.val)
        
        return max(left, right) + root.val

从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解法
一般都是”中序+后序“或者”中序+前序“才能得到二叉树。因为前序和后序可以得到root，后序是最后一个值，前序是第一个值，然后得到root在中序中的位置，就可以分出左右子树，递归就可以了。

# 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 buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not postorder:
            return None
        
        root = TreeNode(postorder[-1])
        n = inorder.index(root.val)
        root.left = self.buildTree(inorder[:n], postorder[:n])
        root.right = self.buildTree(inorder[n+1:], postorder[n:-1])
        
        return root

从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

# 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 buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        n = inorder.index(root.val)
        root.left = self.buildTree(preorder[1:n+1], inorder[:n])
        root.right = self.buildTree(preorder[n+1:], inorder[n+1:])
        
        return root

填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：
在这里插入图片描述

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

解法
因为是完美二叉树，所以会省掉很多边界条件的判断。
常数级空间，所以只能用递归，不能用层次遍历。
观察可得，对于每个节点Node的左孩子Node.left，这个左孩子的next一定是指向它的兄弟节点，即Node.right
对于每个节点Node的右孩子，就得分两种情况讨论：

  • 如果Node.next == None，即Node自己就没有下一个节点，那么Node.right也没有下一个节点。
  • 如果Node有下一个节点, 那么Node.right.next = Node.next.left。
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root or (not root.left and not root.right):
            return root
        
        root.left.next = root.right
        if root.next:
            root.right.next = root.next.left
            
        self.connect(root.left)
        self.connect(root.right)
        
        return root

填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
在这里插入图片描述
解法
不是完美二叉树了，所以需要很多边界条件的分类讨论：

  • 当一个Node既有左孩子又有右孩子的时候，显然左孩子的next就是右孩子，右孩子的next得在Node的next里往右找，直到某个节点有孩子，这个孩子就是Node.right的next。
  • 当一个Node只有左孩子的时候，左孩子的next得在Node的next里往右找。
  • 当一个Node只有右孩子的时候，右孩子的next得在Node的next里往右找。

这道题比较关键的地方在于递归部分要先处理右子树再处理左子树，因为根据上面的分析，找一个节点的next需要用它父亲节点的next一路往右找，所以必须先把右边部分搞定，左子树才能利用正确的next关系进行查找。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root or (not root.left and not root.right):
            return root
        
        #print("root", root.val)
        if root.left:
            if root.right:
                root.left.next = root.right
            else:
                cur = root
                while cur.next:
                    if cur.next.left or cur.next.right:
                        root.left.next = cur.next.left if cur.next.left else cur.next.right
                        break
                    cur = cur.next
        if root.right:
            #print("right", root.right.val)
            cur = root
            while cur.next:
                if cur.next.left or cur.next.right:
                    root.right.next = cur.next.left if cur.next.left else cur.next.right
                    break
                cur = cur.next
            
        self.connect(root.right)
        self.connect(root.left)
        
        return root

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

在这里插入图片描述
说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解法
二叉树的公共祖先有三种情况：

  1. 如果一个节点的左右分别是两个值，那么当前节点一定是公共祖先。
  2. 如果当前节点左树可以找到一个值，当前节点值等于另一个值，那么祖先也就是当前值。
  3. 如果当前节点右树可以找到一个值，当前节点值等于另一个值，那么祖先也一定就是当前值。

对于后两种情况，只需要判断当前节点是否为两个值之一，如果是，就直接返回这个节点。
第一种情况就分别遍历左右子树，并返回任何含有某个值的子树。

# 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 lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        return left or right

二叉树的子结构

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）如图，第二棵树为第一棵树的子树。
在这里插入图片描述
解法
我们是要判断B是不是A的子结构，则B是子树，A为原树。我们可以先找到B的根结点在A树中的位置，然后再看A中该节点之下有没有与B树结构一样的子树。那么这道题就被拆解成两个比较简单的子题目。

# 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 checkSubTree(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: bool
        """
        if not t1:
            return not t2
        if not t2:
            return True

        return self.dfs(t1, t2) or self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)

    def dfs(self, t1, t2):
        if not t1:
            return not t2
        if not t2:
            return True
        if t1.val != t2.val:
            return False
        return self.dfs(t1.left, t2.left) and self.dfs(t1.right, t2.right)

二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解法
参考：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e?answerType=1&f=discussion

  • 模拟法：根据给出的结点求出整棵树的根节点；根据根节点递归求出树的中序遍历，存下；遍历查找当前结点，则当前结点的下一结点即为所求。
  • 分情况：一种情况是节点有右子树的时候，就是要得到右子树的最左节点；另一种情况就是没有右子树的时候，就是找父节点，但是也要分具体情况。

解法二：

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        
        cur = pNode
        if cur.right:
            cur = cur.right
            while cur.left:
                cur = cur.left
            return cur
        
        while cur.next:
            tmp = cur.next
            if tmp.left == cur:
                return tmp
            cur = cur.next
            
        return None

还原二叉树

给了一个字符串表示二叉树，来还原出一颗二叉树，字符串大概是"(a,(b,c,null),(d,(e,f,g),null))


class Tree:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Test:

    def test(self, s):

        if s[1] == 'null':
            return None

        root = Tree(s[1])
        root.left = self.test(s[3:])

        stack = []
        idx = 0
        for i, x in enumerate(s[1:]):
            if x == '(':
                stack.append(x)
            elif x == ')':
                stack.pop()
                if not stack:
                    idx = i

        root.right = self.test(s[idx + 1:])

从右边看二叉树（Binary Tree Right Side View）

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
在这里插入图片描述
解法
题目大意：给定一棵二叉树，想象自己站在树的右边，返回从上到下你能看到的节点的值。

  • 二叉树的层次遍历，每层按照从左向右的顺序依次访问节点（每一层取最右边的节点）。
  • 也可以递归的方法，用一个字典类型存储每行的值，不断更新它。
from collections import deque

class Solution(object):
    def rightSideView(self, root):
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1

        queue = deque([(root, 0)])
        while queue:
            node, depth = queue.popleft()

            if node is not None:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)

                # 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmost_value_at_depth[depth] = node.val

                queue.append((node.left, depth+1))
                queue.append((node.right, depth+1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]


# 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 rightSideView(self, root):
        d = {}
        def f(root, i):   # i为树的深度
            if root:
                d[i] = root.val
                f(root.left, i+1)
                f(root.right, i+1)
        f(root, 0)
        return list(d.values())
版权声明：本文为qq_26919935原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。