Binary tree traversal framework
Just began to brush the binary tree problem, brush while learning, the first contact with the binary tree, recursion is really see people: I am who I am where, sort out the content of today’s learning, review at the same time for their own future reference. If there are any mistakes or omissions, welcome to add to the exchange.
Binary tree traversal framework:
void traverse(TreeNode root){
if(root == null){
returnnull; } // front traverse(root.left);# left subtree// middle traverse with root handler on middle traverse(root.right);# right subtree}}Copy the codeFirst order: root left and right, middle order: left root right; Follow-up: root around their summarizes a traversal peel Onions criterion (recursive recursive process) : strip off to the left (right) node, as long as it has child nodes, his identity to the parent node (the root), at this time his father identity priority is greater than the left (right) node identity, must first consider its children, until it has no children.
Two, traversal examples
A very simple example:
Three, ergodic architecture practice — force deduction
1, 617 merge binary tree
(1) Title:
Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.
You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary tree.
(2) Analysis and answer
You need to start at the root node, so use a sequential traversal framework. You need to merge them into a new binary tree, and make a new tree whose node values are the sum of the corresponding node values of the two trees. Return NULL if both are null.
Class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { Null if both are empty)if (root1==null){
return root2;
}
if (root2==null){
returnroot1; } // The big frame is a sequential traversal: // Define a binary tree where val is equal to the sum of two values // define a new tree where val is equal to the sum of two values // Define a new tree where val is equal to the sum of two values // Define a new tree where val is equal to the sum of two values // TreeNode merge = new TreeNode(root1.val+root2.val); TreeNode merge = new TreeNode(root1.val+root2.val); // Merge the left tree of root1 and the left tree of root2 as the left tree of merge // merge the right tree of root1 and the right tree of root2 as the right tree of merge mergeTrees(root1.left,root2.left); merge.right = mergeTrees(root1.right,root2.right);return merge;
}
Copy the codeThis is the first question about trees. After reading it, I just thought, wow, trees are amazing my mother.
2. 226 Reverse the binary tree
(1) Title
(2) Analysis and answer
I still haven’t written it, read the official answers and comments. “Do these three things (1. Reverse all nodes of the left subtree; 2. Reverse all nodes in the right subtree. 3. Reverse the root node of the left and right subtrees (reverse the root node of the left and right subtrees) determines whether it is pre-reverse, mid-reverse, or post-reverse.
Public TreeNode invertTree(TreeNode root) {if(root == null) returnroot; TreeNode temp = root.left; root.left = root.right; // root root.right = temp; / / root invertTree (root. Left); / / left invertTree (root. Right); / / rightreturnroot; } public TreeNode invertTree(TreeNode root) {if(root == null) returnroot; invertTree(root.left); // Left TreeNode temp = root.left; root.left = root.right; // root root.right = temp; / / root invertTree (root. Left); / / rightreturnroot; } public TreeNode invertTree(TreeNode root) {if(root == null) returnroot; invertTree(root.left); / / left invertTree (root. Right); // right TreeNode temp = root.left; root.left = root.right; // root root.right = temp; / / rootreturnroot; } public TreeNode invertTree(TreeNode root) {if(root == null) return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(! queue.isEmpty()){ TreeNode cur = queue.remove(); TreeNode temp = cur.left; cur.left = cur.right; cur.right = temp;if(cur.left ! = null) queue.add(cur.left);if(cur.right ! = null) queue.add(cur.right); }returnroot; }}Copy the codeThe code above is a bit easier to understand, and the most highly reviewed code is as follows (this one is really confusing to me) :
Public TreeNode invertTree(TreeNode root) {public TreeNode invertTree(TreeNode root) {if (root == null) returnnull; // Save the right subtree TreeNode rightTree = root.right; Root. right = invertTree(root.left); root.left = invertTree(rightTree);returnroot; }} Public TreeNode invertTree(TreeNode root) {if (root == null) returnnull; invertTree(root.left); TreeNode rightNode= root.right; Root. right = root.left; root.left = rightNode; InvertTree root. Left invertTree(root. Left) invertTree root. Public TreeNode invertTree(TreeNode root) {public TreeNode invertTree(TreeNode root)if (root == null) return null;
TreeNode leftNode = invertTree(root.left);
TreeNode rightNode = invertTree(root.right);
root.right = leftNode;
root.left = rightNode;
returnroot; Class Solution {public TreeNode invertTree(TreeNode root) {// TreeNode invertTree(TreeNode root)if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()){ TreeNode node = queue.poll(); TreeNode rightTree = node.right; node.right = node.left; node.left = rightTree;if(node.left ! = null){ queue.offer(node.left); }if (node.right != null){
queue.offer(node.right);
}
}
returnroot; }}Copy the codeWrite your own, and some very interesting ones come up:
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
returnnull; } return TreeNode rightTree = root.right; root.right=invertTree(root.left); root.left=rightTree; The left subtree of this step is equivalent to the right subtree, given the same value. The right subtree of the same level does not recurse downward.return root;
}
Copy the code