Binary tree structure and traversal

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Today we’re going to look at tree traversal, recursive and non-recursive

The structure of the tree

function TreeNode(val, left, right) {
	this.val = (val===undefined ? 0 : val)
	this.left = (left===undefined ? null : left)
	this.right = (right===undefined ? null : right)
}
Copy the code

Tree traversal

Depth-first traversal DFS (recursive)

function DFS(root) {
	if (root === null) return;
	DFS(root.left);
	DFS(root.right);
}
Copy the code

Depth-first traversal DFS (stack)

I don’t have to do this recursively, but you can draw a picture on a piece of paper, and I’ll do a couple more pictures when I have time

function DFS(root) {
  const stack = [];
  stack.push(root);
  
  while (stack.length > 0) {
    root = stack.pop();
    if (root.right) stack.push(root.right);
    if(root.left) stack.push(root.left); }}Copy the code

Breadth-first traversal of BFS (queue)

function BFS(root){
	const queue = [];
	queue.unshift(root);
	
	while(queue.length > 0) {
		root = queue.pop();
		if(root.left) queue.unshift(root.left);
		if(root.right) queue.unshift(root.right); }}Copy the code

Middle order traversal of binary trees

Middle-order traversal traverses the left subtree, then visits the root node, and then traverses the right subtree.

Left-center-right

Leetcode-cn.com/problems/bi…

144. Antecedent traversal of binary trees

Center-left-right

Leetcode-cn.com/problems/bi…

145. Back-order traversal of binary trees

Left-right-middle leetcode-cn.com/problems/bi…

Anterior: root left and right; Middle sequence: left root right; Postsequence: left and right roots; Middle order is often used to obtain increasing ordered sequences in binary search numbers. Postsequence can be used in mathematics suffix notation, combined with stack processing expression, each encountered an operator, you can pop two elements on the top of the stack, calculate and return the result to the stack;

[Solution 1] Recursive DFS

Using recursion, the writing method of the three traversal methods is relatively uniform

/ * * *@param {TreeNode} root
 * @return {number[]}* /
function inorderTraversal(root) {
  // Define a result array to hold the values of the nodes traversed
  const result = [];

  // Define a recursive function
  function inorder(root) {
    // exit recursively until the node is empty
    if (root === null) return;
    
	//
    // Recursive call passed to the left child of the root node
    inorder(root.left);
    // select * from left to right;
    // Put the value of the root node into the Result array
    result.push(root.val);
    // Call recursively, passing in the right child of the root node
    inorder(root.right);
  }

  // Execute the recursive function to represent the current traversal to root
  inorder(root);

  return result;
}

Copy the code

[Solution 2] Non-recursive iteration method – stack

Non-recursively, use a stack

In the sequence traversal

A stack and loop to simulate recursive operations

Iterate through the tree and stack using a while loop

function inorderTraversal(root) {
    const result = []
    const stack = []
    // Walk through the tree, end: node is empty and stack is empty
    while(root || stack.length > 0) {// Iterate over the root node and all its left children
        while(root){
            stack.push(root)
            root = root.left
        }
        // The left child traverses the stack and the top element is off the stack
        root = stack.pop()
        // * * * * * * * * * * * *
        result.push(root.val)
        // Point to the right child, if there is no null, the next loop will unstack an element
        root = root.right
    }

    return result
}
Copy the code

The former sequence traversal

var preorderTraversal = function(root) {
    const result = []
    const stack = []
    while(root || stack.length > 0) {while(root){
        	// 【 foreword: middle - left - right 】
            result.push(root.val)
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        root = root.right
    }
    return result
};
Copy the code

Post-order traversal (heavy and difficult points)

var postorderTraversal = function(root) {
    const result = []
    const stack = []
    // to mark the node
    let prev = null
    while(root || stack.length > 0) {while(root){
        	// Walk through the node left child to the end
            stack.push(root)
            root = root.left
        }
        // push a node off the stack to perform the following operations
        root = stack.pop()
        
        // 【后 置 : left - right - middle 】
        
        // If there is a right child, and the right child is not marked, push the right child to the stack, while traversing the right child
        if(root.right ! = =null&& root.right ! == prev){// The pointer moves to the right, and then loops [right]
			stack.push(root)
			root = root.right
		}else {
			// At this point, there is no right child, or there is a right child, but is marked [middle]
			// Store the value of the node into the result array
			result.push(root.val)
			// The saved nodes are marked
			prev = root
			// The node is cleared
			root = null}}return result
};
Copy the code

【 句 型 3 】Morris is the word in the word “Morris”

Convert a binary tree into a linked list, where each node can have only the right child

function inorderTraversal(root) {
  const result = [];
  let predecessor = null;
  
  while(root ! = =null) {
  
    if (root.left) {
      The predecessor node is the current root node that goes one step to the left and then continues to go right until it can no longer go
      predecessor = root.left;
      
      while(predecessor.right && predecessor.right ! == root) { predecessor = predecessor.right; }// Let the predecessor's right pointer point to root to continue traversing the left subtree
      if(! predecessor.right) { predecessor.right = root; root = root.left; }else {
        // The left subtree has been accessed and we need to disconnect the link
        result.push(root.val);
        predecessor.right = null; root = root.right; }}else {
      // If there is no left child, access the right child directlyresult.push(root.val); root = root.right; }}return result;
}
Copy the code