Tree traversal and its basic operations

Tree traversal and its basic operations

main content:

  1. Recursive and iterative realization of binary tree traversal (pre-order, middle-order, post-order, breadth-first traversal)
  2. The depth of the binary tree, all paths from the binary tree to the leaf nodes

1. define the binary tree class

class TreeNode : def __init__ ( self,x ): self.val=x = self.left None self.right = None duplicated code
class TreeNode {//Tree int val; TreeNode left; TreeNode right; TreeNode( int x) {val = x;} } Copy code

The traversal of the binary tree is divided into depth-first traversal (dfs) and breadth-first traversal (bfs). The depth-first traversal is divided into first-order traversal, middle-order traversal, and post-order traversal. bfs is also called hierarchical traversal.

  • The iterative implementation of dfs uses stack
  • The iterative implementation of bfs uses queue

Traversal of binary tree

Surrounded area

Preorder traversal

Traversal order: root node-left child-right child (ABDECF)

Recursive implementation:

def preorder ( root ): if not root: return print (root.val) preorder(root.left) preorder(root.right) Copy code
public void preorder (TreeNode root) { if (root== null ) return ; System.out.println(root.val); this .preorder(root.left); this .preorder(root.right); } Copy code

Iterative implementation:

def preorder ( root ): stack=[root] while stack: s=stack.pop(- 1 ) if s: print (s.val) stack.append(s.right) stack.append(s.left) Copy code
public void preorder (TreeNode root) { Deque<TreeNode> st = new LinkedList<> (); st.addFirst(root); while (!st.isEmpty()) { TreeNode s=st.pollFirst(); if (s!= null ) { System.out.println(s.val); st.addFirst(s.right); st.addFirst(s.left); } } } Copy code

In-order traversal

Traversal order: left child-root node-right child (DBEACF)

Recursive implementation:

def inorder ( root ): if ( not root): return inorder(root.left) print (root.val) inorder(root.right) Copy code
public void inorder (TreeNode root) { if (root== null ) { return ; } this .inorder(root.left); System.out.println(root.val); this .inorder(root.right); } Copy code

Iterative implementation:

def inorder ( root ): stack=[] while stack or root: while root: #Down loop until the first leaf node is found stack.append(root) root=root.left root=stack.pop(- 1 ) print (root.val) root=root.right Copy code
public void inorder (TreeNode root) { Deque<TreeNode> st = new LinkedList<> (); while (!st.isEmpty() || root!= null ) { while (root!= null ) { st.addFirst(root); root=root.left; } root=st.pollFirst(); System.out.println(root.val); root=root.right; } } Copy code

Post-order traversal

Traversal order: left child-right child-root node (DEBFCA)

Recursive implementation:

def postorder ( root ): if ( not root): return postorder(root.left) postorder(root.right) Print (root.val) copying the code
public void postorder (TreeNode root) { if (root== null ) return ; this .postorder(root.left); this .postorder(root.right); System.out.println(root.val); } Copy code

Iterative implementation:

def postorder ( root ): stack=[] while stack or root: while root: #Down loop until the first leaf node is found stack.append(root) if root.left: #Left child pushes the stack, if there is no left child, the right child pushes the stack root=root.left else : root=root.right s=stack.pop(- 1 ) print (s.val) #If the current node is the left child of the top node of the stack, traverse the right child if stack and s==stack[- 1 ].left: root=stack[- 1 ].right else : = the root None duplicated code

Level traversal

Traverse order: traverse layer by layer (ABCDEF)

Iterative implementation:

def bfs ( root ): queue=[root] while queue: n = len (queue) for i in range (n): q=queue.pop( 0 ) if q: print (q.val) queue.append(q.left if q.left else None ) queue.append (q.right IF q.right the else None ) copying the code
public void bfs (TreeNode root) { if (root== null ) return ; Queue<TreeNode> q = new LinkedList<> (); q.offer(root); while (!q.isEmpty()) { int n=q.size(); while (n> 0 ) { TreeNode node=q.poll(); System.out.println(node.val); if (node.left!= null ) { q.offer(node.left); } if (node.right!= null ) { q.offer(node.right); } n--; } } } Copy code

Basic operation

Finding the depth, diameter, and longest path of the same value of the binary tree is actually a process of post-order traversal

Maximum depth of binary tree

DEF maxDepth ( the root ): IF Not the root: return 0 return . 1 + max (maxDepth (root.left), maxDepth (root.right)) copying the code
public int maxDepth (TreeNode root) { if (root== null ) return 0 ; return Math.max( this .maxDepth(root.left), this .maxDepth(root.right))+ 1 ; } Copy code

Diameter of the tree

Diameter of the tree

class Solution { int dia= 0 ; public int diameterOfBinaryTree (TreeNode root) { depth(root); return dia; } private int depth (TreeNode root) {//Calculate the diameter of each subtree in the process of finding the height of the tree if (root== null ) return 0 ; int l=depth(root.left); int r=depth(root. right); dia=Math.max(dia, l+r); return Math.max(l, r)+ 1 ; } } Copy code

Longest path of the same value

Longest path of the same value

class Solution { int res; public int longestUnivaluePath (TreeNode root) { maxLen(root); return res; } private int maxLen (TreeNode root) {//Find the longest path with the same value starting from root if (root== null ) { return 0 ; } int l=maxLen(root.left); int r=maxLen(root.right); if (root.left!= null ) { if (root.left.val==root.val) { l+= 1 ; } else { l = 0 ; } } if (root.right!= null ) { if (root.right.val==root.val) { r+= 1 ; } else { r = 0 ; } } res=Math.max(res, l+r); return Math.max(l, r); } } Copy code

The maximum path sum in the binary tree

The maximum path sum in the binary tree

class Solution { int res; public int maxPathSum (TreeNode root) { res=root.val; //Pay attention to the initial value of res, the path requires at least one node maxSum(root); return res; } private int maxSum (TreeNode root) { if (root== null ) { return 0 ; } int l=maxSum(root.left); if (l< 0 ){ l = 0 ; } int r=maxSum(root.right); if (r< 0 ){ r = 0 ; } res=Math.max(res, l+r+root.val); return Math.max(l+root.val, r+root.val); } } Copy code

The sum of the left leaves

leetcode-cn.com/problems/su...

Recursion: the sum of the left leaves of the tree = the sum of the left leaves of the left subtree + the sum of the left leaves of the right subtree + the value of the current leaf node (if the current node is the left child of the parent node)

The point is to determine whether the current node is the left child of its parent node, so the parameter dir is passed in the recursive function to indicate the left child/right child

class Solution { public int sumOfLeftLeaves (TreeNode root) { return leftSum(root, 1 ); } private int leftSum (TreeNode root, int dir) {//0 represents the left child, 1 is the right child int sum = 0 ; if (root== null ) { return 0 ; } if (root.left== null && root.right== null && dir== 0 ) { return root.val; } sum+=leftSum(root.left, 0 ); sum+=leftSum(root.right, 1 ); return sum; } } Copy code

Convert binary search tree to accumulative tree

Convert binary search tree to accumulative tree

BST mid-order traversal is in ascending order, and vice versa, descending order, and then accumulate to the current node.

class Solution { int num= 0 ; public TreeNode convertBST (TreeNode root) { if (root== null ) return null ; convertBST(root.right); root.val+=num; num=root.val; convertBST(root.left); return root; } } Copy code

Nearest common ancestor of binary tree

Nearest common ancestor of binary tree

Post-order traversal

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 left and right: # p, q are on the opposite side of root respectively return root if not left and not right: # root's left/right subtree does not contain p, q return None if left: # p, q are not present root of the right subtree return left IF right: # the p-, q is not in the root of the left subtree return right copy the code

Build a binary tree

A binary tree can be constructed according to the preorder and the middle order, and a binary tree can also be constructed according to the postorder and the middle order. Anyway, the middle order can be constructed. Because there is no in-order, the shape of the tree cannot be determined. For example, a tree whose first order is [1,2] and subsequent order [2,1] can have:

1 / 2 Copy code
1 / 2 Copy code

The idea of binary tree problem is mostly recursion, which is to divide the sub-problems, and then recursively build the left subtree and the right subtree.

The last node of the post-order traversal is the root node of the entire tree, so the root node can be determined.

According to the middle sequence, the middle sequence of the left subtree and the middle sequence of the right subtree are obtained.

Regardless of the middle order or the post order, the number of nodes in the left and right subtrees is the same, so the post order sequence of the left subtree and the right subtree can be obtained.

Recursively construct the left and right subtrees.

See the code from the sequence order and postorder binary tree structure , the former order and configured binary sequence preorder