【Leetcode】top 100 二叉树

基础知识补充

完全二叉树：顺序存储（数组）

非根节点的父节点序号floor((i-1)/2)

序号i的左孩子节点序号2*i+1 右孩子节点序号2*i+2

一般二叉树：链式存储

结构：left指针指向左子节点，right指针指向右子节点，data存储数据项；
class TreeNode(object):        
    def __init__(self, data, left=None, right=None):        
        self.data = data            
        self.left = left            
        self.right= right           
平衡二叉树：左子树和右子树的高度之差的绝对值不超过1，且左子树和右子树也是平衡二叉树；

二叉搜索树：左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值，且左子树和右子树也是二叉搜索树

基础操作补充

1. 二叉树的插入

先判断父节点是否存在，再判断左子节点是否存在；构建右子节点后需要弹出父节点；

class BinTree():
    def _init__(self):
        self.root = None 
        self.ls =[]

    def add(self,data):
        node = TreeNode(data)
        if self.root == None:
            self.root = node
            self.ls.append(self.root)
        else:
            rootNode = self.ls[0]
            if rootNode.left == None:
                rootNode.left = node
                self.ls.append(rootNode.left)
            elif rootNode.right == None:
                rootNode.right = node
                self.ls.append(rootNode.right)
                
                self.ls.pop(0)          #弹出子树已满的节点

2. 二叉树的遍历

前序遍历（深度优先）当前节点-当前节点的左子树-当前节点的右子树递归或栈实现

中序遍历（深度优先）当前节点的左子树-当前节点-当前节点的右子树递归或栈实现

后序遍历（深度优先）当前节点的左子树-当前节点的右子树-当前节点递归或栈实现

层序遍历（广度优先）各层级中从左到右的遍历队列实现

已知两种二叉树遍历序列（其中需要包括中序遍历）可以唯一确定一棵二叉树；

#前序遍历的递归实现    
    def preOrderTraversal(self,root):  
        if root == None: return
        print(root.data)
        self.preOrderTraversal(root.left)
        self.preOrderTraversal(root.right)

#前序遍历的栈实现
    def preOrderStack(self,root):     
        if root == None:return
        stack =[]   #存放节点
        result =[]  #存放节点值
        node = root
        while node or stack:
            while node:              
                result.append(node.data)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
        print(result)

#中序遍历的递归实现
    def inOrderTraversal(self,root):  
        if root == None: return
        self.preOrderTraversal(root.left)
        print(root.data)
        self.preOrderTraversal(root.right)

#中序遍历的栈实现
    def inOrderStack(self,root):     
        if root == None:return
        stack =[]   #存放节点
        result =[]  #存放节点值
        node = root
        while node or stack:
            while node:              
                stack.append(node)
                node = node.left
            node = stack.pop()
            result.append(node.data)
            node = node.right
        print(result)

#后序遍历的递归实现
    def postOrderTraversal(self,root):  
        if root == None: return
        self.preOrderTraversal(root.left)
        self.preOrderTraversal(root.right)
        print(root.data)

#后序遍历的栈实现
    def inOrderStack(self,root):     
        if root == None:return
        stack =[]   #存放节点
        result =[]  #存放节点值
        seq = []
        node = root
        while node or stack:           #左-右-根视为根-右-左（前序的左右互换）的逆序
            while node:     
                seq.append(node.data)         
                stack.append(node)
                node = node.right      #内外层左右互换
            node = stack.pop()
            node = node.left
        while seq:
            result.append(seq.pop())   #逆序
        print(result)

#层序遍历的队列实现
    def levelOrder(seLf, root):       
        if root == None:return
        queue =[]
        result =[]
        node = root
        queue.append(node)
        while queue:
            node = queue.pop(0)
            result.append(node.data)
            if node.left != None:queue.append(node.left)
            if node.right != None:queue.append(node.right)
        print(result)

题目

94 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

方法一：递归实现

方法二：栈实现

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        if root == None: return
        stack = []
        result = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            result.append(node.val)
            node = node.right
        return result

方法三：颜色标记法：给每个节点一个访问状态，未访问为白，已访问为黑；

中序出栈顺序：左-中-右对应的入栈顺序：右-中-左栈：先进后出

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        white, black = 0, 1
        result = []
        stack = [(white, root)]
        while stack:                         
            color, node = stack.pop()
            if node is None:continue
            if color == white:
                stack.append((white, node.right))
                stack.append((black, node))
                stack.append((white, node.left))      # 适用于前中后序遍历，改变这里位置即可
            else:
                result.append(node.val)
        return result

方法四：莫里斯遍历

思路：如果左节点不为空，就将当前节点和右子树全部挂在左子树的最右子树下；

如果左节点为空，打印节点，并向右遍历；

class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		pre = None
		while root:
			# 如果左节点不为空，就将当前节点连带右子树全部挂到左节点的最右子树下面
			if root.left:
				pre = root.left
				while pre.right:
					pre = pre.right
				pre.right = root          
				tmp = root             
				root = root.left       # 切换到左子树的父节点
				tmp.left = None        # 取消当前节点到左子树的链接
			# 左子树为空，则打印这个节点，并向右边遍历	
			else:
				res.append(root.val)
				root = root.right
		return res

104 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

方法一：二叉树最大深度 = max(左子树高度，右子树高度)+1

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None: return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1

方法二：用临时队列维护每层节点，一层结束后将深度+1

class Solution:
    def maxDepth(self, root):
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res

226 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

方法一：用栈做中序遍历：

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            node.left, node.right = node.right, node.left
            node = node.left
        return root

方法二：用队列做层级遍历

class Solution(object):
	def invertTree(self, root):
		"""
		:type root: TreeNode
		:rtype: TreeNode
		"""
		if root is None:return
		queue = [root]
		while queue:
			tmp = queue.pop(0)
			tmp.left,tmp.right = tmp.right,tmp.left
			if tmp.left:queue.append(tmp.left)
			if tmp.right:queue.append(tmp.right)
		return root

方法三：递归实现

class Solution(object):
	def invertTree(self, root):
		"""
		:type root: TreeNode
		:rtype: TreeNode
		"""
		if root is None: return
		root.left,root.right = root.right,root.left
		self.invertTree(root.left)
		self.invertTree(root.right)		
		return root

101 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

方法一：用队列做层级遍历，判断每层节点是否对称

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        quece = [root]
        while quece:
            tmp = []
            val = []
            for node in quece:
                if node.left:
                    tmp.append(node.left)
                    val.append(node.left.val)
                else:val.append(101)                # 101是节点值范围之外的数
                if node.right:
                    tmp.append(node.right)
                    val.append(node.right.val)
                else:val.append(101)
            if val != val[::-1]:return False        # 耗时
            quece = tmp
        return True 

# 不用滚动队列的话就一次性考虑两个节点，并在放置时将需要比较的节点相邻放置
class Solution(object):
	def isSymmetric(self, root):
		"""
		:type root: TreeNode
		:rtype: bool
		"""
		if not root or not (root.left or root.right):return True	
		queue = [root.left,root.right]
		while queue:
			left = queue.pop(0)      
			right = queue.pop(0)
			if not (left or right):  # 两个节点都为空
				continue
			if not (left and right): # 两个节点中有一个为空
				return False
			if left.val!=right.val:  # 两个节点的值不相等
				return False

			queue.append(left.left)
			queue.append(right.right)
		
			queue.append(left.right)
			queue.append(right.left)

		return True

方法二：递归实现

class Solution(object):
	def isSymmetric(self, root):
		"""
		:type root: TreeNode
		:rtype: bool
		"""
		if not root: return True
		def dfs(left,right):
			if not (left or right):   # 两个节点都为空
				return True
			if not (left and right):  # 两个节点中有一个为空
				return False
			if left.val!=right.val:   # 两个节点的值不相等
				return False
			return dfs(left.left,right.right) and dfs(left.right,right.left)

		return dfs(root.left,root.right)

543 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。

分析：直径 = 左子树到父节点的最长路径 + 右子树到父节点的最长路径

左/右子树到父节点的最长路径 = 左/右子树深度

子树深度不用重复计算：height = max(左子树深度，右子树深度)+1

方法一：使用全局变量

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        global maxx 
        maxx = 0
        def depth(root):
            if root is None:return 0
            left = depth(root.left)
            right = depth(root.right)
            global maxx
            maxx = max(maxx, left+right)
            return max(left, right)+1
        
        depth(root)
        return maxx

方法二：不使用全局变量

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        depth, length = self.depth(root)
        return length

    def depth(self, root):
        if root is None:return (0, 0)
        left_depth, left_length = self.depth(root.left)
        right_depth, right_length = self.depth(root.right)

        depth = max(left_depth, right_depth) + 1
        length = max(left_length, right_length, left_depth + right_depth)
        return depth, length

102 层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

方法一：两个数组实现

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:return []
        quece, result = [root], []
        while quece:                            
            tmp_res, tmp_que = [], [] 
            while quece:
                node = quece.pop(0)
                tmp_res.append(node.val)
                if node.left:tmp_que.append(node.left)
                if node.right:tmp_que.append(node.right)
            result.append(tmp_res)
            quece = tmp_que                                 
        return result

方法二：一个数组实现，用变量确定每层需要处理的子节点数即可正常插入数组；

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:return []
        quece, result = [root], []
        while quece:     
            length = len(quece)                       
            tmp_res = [] 
            for i in range(length):
                node = quece.pop(0)
                tmp_res.append(node.val)
                if node.left:quece.append(node.left)
                if node.right:quece.append(node.right)
            result.append(tmp_res)                                
        return result

108 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

针对平衡，同时添加左子树和右子树；针对搜索，将数组确定父节点后进行二分；

递归实现

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        def balanceTree(left, right):
            if left > right: return None
            mid = (left+right)//2
            root = TreeNode(nums[mid])
            root.left = balanceTree(left, mid-1)
            root.right = balanceTree(mid+1, right)

        left, right = 0, len(nums)-1
        return balanceTree(left, right)

98 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

方法一：验证：左子节点值<父节点值<右子节点值 不够准确

在验证10的右子树时，首先所有值要大于10，即需要记录左右子树的不同边界值（左子树-上界右子树-下界）

对于节点6来说，先在右子树确定下界为10，再在左子树确定上界为15，而6不属于这个区间；
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        def isBST(node, low, up):
            if node is None:return True
            if node.val<=low or node.val>=up: return False
            return isBST(node.left,low,node.val) and isBST(node.right,node.val,up)
        
        return isBST(root, -2**31-1, 2**31)   # 题目范围的边界值
方法二：利用"二叉搜索树的中序遍历一定升序排列"性质；

在构建中序遍历数组的同时可以进行升序比较；

230 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

利用"二叉搜索树的中序遍历一定升序排列"性质；构建中序遍历数组后直接取出第k个值即可；不构建中序遍历数组的话也可以选择对k处理（在需要插入值的位置将k减一，k归零时对应输出）；

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack = []
        result = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            result.append(root.val)
            root = root.right
        return result[k-1]

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0: return root.val
            root = root.right

199 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

返回层序遍历数组每层的最后一个值；

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:return []
        quece, result = [root], []
        while quece:     
            length = len(quece)                       
            tmp_res = [] 
            for i in range(length):
                node = quece.pop(0)
                tmp_res.append(node.val)    
                # if i == length-1: result.append(node.val) 
                if node.left:quece.append(node.left)
                if node.right:quece.append(node.right)
            result.append(tmp_res[-1])                                
        return result

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

方法一：颜色标记法：出栈要求中-前-后，入栈则是右-前-中

需要创建虚拟链表头结点；

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        white, black = 0, 1
        stack = [(white, root)]
        head = TreeNode(0)
        pre_node = head
        while stack:
            color, node = stack.pop()
            if color == white:
                if node.right:stack.append((white, node.right))
                if node.left:stack.append((white, node.left))
                stack.append((black, node))
            else:
                node.left = None
                pre_node.right = node
                pre_node = node
        return head.right

方法二：找到链表的前置节点

对于当前节点，需要将其左子树的根节点移到右侧才能满足链表要求，而其右子树的根节点在链表中需要接在左子树最右结点之后。

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        node = root
        while node:
            if node.left:
                left_node = left_last_node = node.left
                while left_last_node.right:
                    left_last_node = left_last_node.right
                left_last_node.right = node.right
                node.left = None
                node.right = left_node
            node = node.right
        return root

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

前序遍历：中-左-右

中序遍历：左-中-右

前序遍历的第一个元素为根节点，在中序遍历序列找到根节点后就能将元素二分为左子树元素和右子树元素，再在前序遍历序列中找到左子树的根节点和右子树的根节点，...
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        
        def bulidThree(preorder, inorder):
            if preorder:
                root = TreeNode(preorder[0])
                idx = inorder.index(preorder[0])

                inorder_left = inorder[:idx]
                inorder_right = inorder[idx+1:]

                preorder_left = preorder[1:idx+1]
                preorder_right = preorder[idx+1:]

                root.left = bulidThree(preorder_left, inorder_left)
                root.right = bulidThree(preorder_right, inorder_right)
                return root
            else:return
        
        return bulidThree(preorder, inorder)
每次查找根节点坐标会造成时间浪费，可以用hashmap存储（空间换时间）

437 路径总和III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

统计从根节点出发到每个子节点的数值和，用不同节点的数值和做差得到截选的路径（类似前缀和想法）

需要在退出当前节点时更新前缀和（保证路径方向向下）

class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: int
        """
        global out
        cur_sum, out = 0, 0
        hash = {0:1}             # 初始化，不然根节点与目标值相等时只能插入hash

        def partSum(root, targetSum, hash, cur_sum):
            if root is None: return 0

            global out

            cur_sum += root.val

            if targetSum - cur_sum in hash: 
                out += hash[targetSum-cur_sum]

            if cur_sum in hash:hash[cur_sum] += 1      # 有正有负，会出现重复的前缀和
            else:hash[cur_sum] = 1

            partSum(root.left, targetSum, hash, cur_sum)
            partSum(root.right, targetSum, hash, cur_sum)

            hash[cur_sum] -= 1
            cur_sum -= root.val
        
        partSum(root, targetSum, hash, cur_sum)
        
        return out

236 二叉树的最近公共祖先

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

对于当前节点，若能从其左子树中找到p/q并从其右子树中找到q/p，则该节点为最近公共祖先节点；

若左侧无p/q，则pq均在右子树，将当前节点切换到当前右子节点；

终止条件：切换到叶子节点或找到p/q；
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root==p or root==q or root==None: return root
        
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        
        if left and right:return root
        if left and right==None:return left
        if right and left==None:return right

124 二叉树的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

和543相似的思路，只是不再记录深度而是路径和；

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        global max_sum 
        max_sum = -1001     # 题目给出的节点的值的下界
        def partPathSum(root):
            if root is None:return 0

            left = partPathSum(root.left)
            left = max(left, 0)                # 除去负值
            right = partPathSum(root.right)
            right = max(right, 0)

            global max_sum
            max_sum = max(max_sum, root.val+left+right)

            return root.val+max(left, right)
        
        partPathSum(root)
        return max_sum