剑指offer之(树)

作者: 桃之夭夭的简书 | 来源:发表于2020-04-20 23:13 被阅读0次

树

写这个文章的目的是为了记录，好背。

树的遍历和树的深度是基础，很多题都是在遍历的基础上加些限制条件，下边题目的排序是我根据我认为的题目难度排序的，最简单基础的排在前面，一些遍历和树深度的变形题目放在后边
题目列表摆在前面：

55-I题二叉树的深度
55-II题平衡二叉树
28题：对称二叉树
27题：二叉树的镜像
面试题32-I 从上到下打印二叉树 I
面试题32 - II. 从上到下打印二叉树 II
面试题32 - III. 从上到下打印二叉树 III
面试题37. 序列化二叉树
面试题54. 二叉搜索树的第k大节点
面试题07. 重建二叉树
面试题34. 二叉树中和为某一值的路径
面试题68 - I. 二叉搜索树的最近公共祖先
面试题68 - II. 二叉树的最近公共祖先
面试题26. 树的子结构

面试题55 - I. 二叉树的深度

递归：

class Solution:
    def TreeDepth(self, root):
        # write code here
        if not root:
            return 0
        return 1 + max(self.TreeDepth(root.left), self.TreeDepth(root.right))

迭代：

class Solution:
    def TreeDepth(self, pRoot):
        # write code here

        depth = 0
        stack = []
        if pRoot:
            stack.append((1, pRoot))
        while stack:
            curr_depth, node = stack.pop()
            if node is not None:
                depth = max(depth, curr_depth)
                stack.append((curr_depth+1, node.left))
                stack.append((curr_depth+1, node.right))
                
        return depth

面试题55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]

返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

class Solution:
    def Permutation(self, nums):
        # write code here
        res = []
        if not nums:
            return []
        nums="".join((lambda x:(x.sort(),x)[1])(list(nums)))
        self.dfs(nums, '', res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
        for i in xrange(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], path+nums[i], res)

解法2，使用二叉树的深度做题

class Solution:
    def IsBalanced_Solution(self, root):
        # write code here
        if not root:
            return True
        left = self.depth(root.left)
        right = self.depth(root.right)
        if abs(left-right)>1:
            return False
        return self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)
         
    
    def depth(self, root):
        if not root:
            return 0
        return 1 + max(self.depth(root.left), self.depth(root.right))

面试题28. 对称的二叉树

检查一棵树是否是对称二叉树
递归：

class Solution:
    def isSymmetrical(self, root):
        # write code here
        if root is None:
            return True
        return self.dfs(root.left, root.right)
    
    def dfs(self, p, q):
        if p is None and q is None:
            return True
        if (p is None or q is None) or p.val != q.val:
            return False
        return self.dfs(p.left, q.right) and self.dfs(p.right, q.left)

迭代写法：

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        stack = [(root.right, root.left)]
        while stack:
            r, l = stack.pop()
            if not l and not r:
                continue
            if (not l or not r) or l.val != r.val:
                return False
            stack.append((l.right, r.left)) #对比左子树的右边，和右子树的左边 
            stack.append((l.left, r.right)) #左子树的左边，和右字数的右边
            print("left: %d, right: %d"%(l.val, r.val))  #这是我测试玩的
        return True

面试题27. 二叉树的镜像

输入一个二叉树，该函数输出它的镜像

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        tmp = root.left
        root.left = self.mirrorTree(root.right)
        root.right = self.mirrorTree(tmp)
        return root

面试题32 - I. 从上到下打印二叉树

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

返回：[3,9,20,15,7]
提示：节点总数 <= 1000
二叉树的层次遍历，没啥好说的。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop(0)
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        return result

面试题32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：[ [3], [9,20], [15,7]]
提示：节点总数 <= 1000

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            tmp = []
            for _ in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            result.append(tmp)
        return result

面试题32 - III. 从上到下打印二叉树 III

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            tmp = []
            for _ in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            result.append(tmp[::-1] if len(result) % 2 else tmp)  #相比上一题就这加了个翻转的判断
        return result

面试题37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：

序列化为 "[1,2,3,null,null,4,5]"

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        就是层次遍历的迭代写法
        """
        if not root: return "[]"
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else: res.append("null")
        return '[' + ','.join(res) + ']'


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        

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

面试题54. 二叉搜索树的第k大节点

二叉树的中序遍历
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1

输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

输出: 4
限制：1 ≤ k ≤ 二叉搜索树元素个数

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        def dfs(root):
            if not root:
                return
            dfs(root.right)
            if self.k == 0:
                return
            self.k -= 1
            if self.k == 0:
                self.res = root.val
            
            dfs(root.left)
        
        self.k = k
        dfs(root)
        return self.res

面试题07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

限制：0 <= 节点个数 <= 5000

解题思路

主要利用二叉树的前中后序的特性
前序遍历特点：节点按照 [ 根节点 | 左子树 | 右子树 ] 排序，以题目示例为例：[ 3 | 9 | 20 15 7 ]
中序遍历特点：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序，以题目示例为例：[ 9 | 3 | 15 20 7 ]
根据题目描述输入的前序遍历和中序遍历的结果中都不含重复的数字，其表明树中每个节点值都是唯一的。
递归写法

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        root = TreeNode(preorder.pop(0))
        index = inorder.index(root.val)
        
        root.left = self.buildTree(preorder, inorder[:index])
        root.right = self.buildTree(preorder, inorder[index+1:])
        return root

迭代写法：
TODO

面试题34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，

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

[[5,4,11,2], [5,8,4,5]]

解题思路

初始化：结果列表 res ，路径列表 path 。
返回值：返回 res 即可。
recur(root, tar) 函数：

递推参数：当前节点 root ，当前目标值 tar 。
终止条件：若节点 root 为空，则直接返回。
递推工作：
路径更新：将当前节点值 root.val 加入路径 path ；
目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 00 ）；
路径记录：当 ① root 为叶节点且 ② 路径和等于目标值，则将此路径 path 加入 res 。
先序遍历：递归左 / 右子节点。
路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res, path = [], []
        def recur(root, target):
            if not root:
                return
            path.append(root.val)
            target -= root.val
            if target == 0 and not root.left and not root.right:
                res.append(list(path))
            
            recur(root.left, target)
            recur(root.right, target)
            
            path.pop()
        
        recur(root, sum)
        return res

面试题68 - I. 二叉搜索树的最近公共祖先

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

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

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

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return False
        if p.val >root.val and q.val >root.val:
            self. lowestCommonAncestor(root.right, p, q)
        elif p.val <root.val and q.val <root.val:
            self. lowestCommonAncestor(root.left, p, q)
        else:
            return root

面试题68 - II. 二叉树的最近公共祖先

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

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

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> 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 not left:
            return right
        if not right:
            return left
        return root

面试题26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

给定的树 B：

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000

解题思路

若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：

先序遍历树 A 中的每个节点 n_A 对应函数 isSubStructure(A, B)）
判断树 A 中以 n_A 为根节点的子树是否包含树 B 。（对应函数 recur(A, B)）

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B:
                return True
            if not A or A.val != B.val:
                return False
            
            return recur(A.left, B.left) and recur(A.right, B.right)
        
        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

剑指offer之(树)

树

面试题55 - I. 二叉树的深度

面试题55 - II. 平衡二叉树

面试题28. 对称的二叉树

面试题27. 二叉树的镜像

面试题32 - I. 从上到下打印二叉树

面试题32 - II. 从上到下打印二叉树 II

面试题32 - III. 从上到下打印二叉树 III

面试题37. 序列化二叉树

面试题54. 二叉搜索树的第k大节点

面试题07. 重建二叉树

解题思路

面试题34. 二叉树中和为某一值的路径

解题思路

面试题68 - I. 二叉搜索树的最近公共祖先

面试题68 - II. 二叉树的最近公共祖先

面试题26. 树的子结构

解题思路

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Algorithms