Ergodic summary of binary trees
Binary tree
In my opinion, binary number is to add next nodes with left and right nodes on the basis of linked list, that is, left and right child nodes, through which a binary number is connected in series. A tree of left and right nodes under the root node, also called a left and right subtree.
How do I manipulate binary trees
The operation of binary tree is nothing more than traversal binary tree, there are three traversal of binary number: pre-order traversal, middle-order traversal, follow-up traversal, also known as depth-first traversal, breadth-first traversal, traversal also mainly need two kinds of recursion, iteration, binary tree fire data structure is as follows:
var node = {
val : 1 ,
left : { // left is the left child node
xxx // Indicates the next node
},
right: {// Right left child node
xxxx // Indicates the next node}}Copy the codeLeedcode bo
First, the most basic is how to recursively and iteratively traverse binary trees to find their commonalities:
Pre-middle and subsequent traversal of binary trees (leecode144, 94, 145)
Leetcode-cn.com/problems/bi… (preorder traversal of binary tree) leetcode-cn.com/problems/bi… (middle order traversal of binary tree) leetcode-cn.com/problems/bi… (Post-order traversal of binary tree)
The idea of traversal before and after (recursion)
- The current node is null-terminated recursion
- Continuation: Add the current node to the result and recurse to the left and right subtrees
- Continuation: first recurse the left subtree, after the end of the left subnumber recursion, add the current node to the result, and then recurse the right subtree
- Follow-up: first recurse the left and right subtrees in turn. After the end of the left and right recursion, add the current node to the result.
Complexity analysis
Time complexity: O(n) Space complexity: O(n)
// continue through
var preorderTraversal = function(root) {
var res= []
var dfs = (root) = > {
if(! root)return
res.push(root.val)
dfs(root.left)
dfs(root.right)
}
dfs(root)
return res
};
// continue to iterate
var preorderTraversal = function(root) {
var res= []
var dfs = (root) = > {
if(! root)return
dfs(root.left)
res.push(root.val)
dfs(root.right)
}
dfs(root)
return res
};
// subsequent traversal
var preorderTraversal = function(root) {
var res= []
var dfs = (root) = > {
if(! root)return
dfs(root.left)
dfs(root.right)
res.push(root.val)
}
dfs(root)
return res
};
Copy the codeThe idea of traversal before and after (iteration)
- You can simulate a stack, with the same details as recursion
Complexity analysis
Time complexity: O(n)
Space complexity: O(n)
Five lines of code to go through before and after
// continue through
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
res.push(root.val) // The continuation first pushes the value into the result
stack.push(root) // all left subtrees are pushed in sequence
root = root.left
}
root = stack.pop() // Unstack if there is no right node continue to unstack
root = root.right
}
return res
};
// continue to iterate
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
stack.push(root) // All left subtrees are pushed in sequence
root = root.left
}
root = stack.pop() / / out of the stack
res.push(root.val) // Push the current value of the value into the result
root = root.right
}
return res
};
// subsequent traversal
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
res.push(root.val) // First push the value into the result
stack.push(root) // all right subtrees are pushed in sequence through the root node
root = root.right
}
root = stack.pop() // Unstack if there is no left node continue to unstack
root = root.left
}
return res.reverse() // The order of traversal is right to left, and the last one is right to left => left and right roots
};
Copy the codeIt can be found that I only changed five lines of code and changed their order to complete the pre-middle and subsequent traversal. The pre-middle and post-middle iteration framework is roughly as follows:
While (root) {res.push(root.val) // first push the value to the result stack.push(root) root = root.right} root = stack.pop() // out of the stack root = root.leftCopy the codeSequence Traversal of binary Trees (BFS) (Leecode102)
Leetcode-cn.com/problems/bi…
Given a binary tree, return the value of the nodes traversed in order. Sequential traversal is to access all nodes layer by layer from left to right
Train of thought
Breadth-first traversal is a layer-by-layer approach that traverses the nodes of each layer. The requirement is to return the node values of each layer, so using breadth-first is quite appropriate.
var levelOrder = function(root) {
if (root === null) return []
var arr = [] // Breadth-first requires queues as auxiliary structures
var res = []
arr.push(root)
while(arr.length ! = =0) {
var array = []
var size = arr.length
for(var i = 0; i<size; i++) {var cur = arr.shift() // Take out the root node first
array.push(cur.val)
if(cur.left! =null) { // If the left/right subtrees are not empty, they are queued.
arr.push(cur.left)
}
if(cur.right! =null) {
arr.push(cur.right)
}
}
// After the first processing, the root node has been removed from the queue, and the root node's two children have been queued
res.push(array) // Save the result each time
// Each loop removes all nodes from the queue and then places the children in the queue.
}
return res
};
Copy the code