Binary tree of algorithms

Hierarchical traversal of a binary tree

Topic describes

Given a binary tree, return a bottom-up hierarchical traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

The sample

Input: given a binary tree [3,9,20,null,null,15,7],

Return value: [[15,7],[9,20],[3]

Their thinking

Use NEx to save the leaf nodes of each level and TMP to save the node values of each level, traversing from top to bottom and from left to right for each level. Finally, reverse the list.

class TreeNode(object):
	"""docstring for TreeNode"""
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution(object):
	"""docstring for Solution"""
	def levelOrderBottom(self, root):
		if root == None: return []
		res = []
		def dfs(root):
			queue = [root]
			while queue:
				nex = []
				tmp = []
				for node in queue:
					tmp.append(node.val)
					if node.left:
						nex.append(node.left)
					if node.right:
						nex.append(node.right)
				res.append(tmp)
				queue = nex
		dfs(root)
		return res[::-1]

node1 = TreeNode(1)
node2 = TreeNode(3)
node3 = TreeNode(4)
node1.left = None
node1.right = node2
node2.left = node3
node2.right = None

solution = Solution()
print(solution.levelOrderBottom(node1))
Copy the code

• Time complexity: O(n)
• Space complexity: O(n)

Symmetric binary tree

Topic describes

Given a binary tree, check whether it is mirror – symmetric.

The sample

Input: the binary tree [1,2,2,3,4,4,3] is symmetric.

Return value: True

Input: [1,2,2,null,3,null,3] is not mirrored.

Return value: False

Their thinking

Using recursive thinking, left and right subtrees are symmetric if the left node of the left subtree is equal to the right node of the right subtree and the right node of the left subtree is equal to the left node of the right subtree.

class TreeNode(object): """docstring for TreeNode""" def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): """docstring for Solution""" def isSymmetric(self, root): def check(node1, node2): if not node1 and not node2: return True elif not node1 or not node2: return False if node1.val ! = node2.val: return False return check(node1.left, node2.right) and check(node1.right, node2.left) return check(root, root)Copy the code

• Time complexity: O(n)
• Space complexity: O(n)

The same tree

Topic describes

Given two binary trees, write a function to check if they are the same.

Two trees are considered identical if they are structurally identical and the nodes have the same value.

The sample

Input: [1,2,3], [1,2,3]

Return value: True

Input: [1,2], [1, NULL,2]

Return value: False

Their thinking

Use recursion to judge that the root nodes of two binary trees are the same and the left and right subtrees are the same tree.

class TreeNode(object):
	"""docstring for TreeNode"""
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if p == None or q == None: return False
        if p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else:
            return False
Copy the code

• Time complexity: O(n)
• Space complexity: O(n)

The maximum depth of a binary tree

Topic describes

Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

The sample

Input: given binary tree [3,9,20,null,null,15,7]

Return value: 3

Their thinking

BFS breadth-first search, using a double-ended Queue deque (because performance is much better than the other two types of queues), traverses each layer of the binary tree once in a large loop, range(len(Queue)) making only the current layer traversed, ans increments 1 for each large loop. Because each node is accessed only once, time complexity O(n)

import collections class TreeNode: """docstring for TreeNode""" def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): """docstring for Solution""" def maxDepth(self, root): if not root: Return 0 queue = collections.deque() # deque append: append(root) ans = 0 while queue: Ans += 1 for I in range(len(queue)): # deque popleft: queue.append(node.left) if node.right: queue.append(node.right) return ansCopy the code

• Time complexity: O(n)
• Space complexity: O(n)