[binary tree 1.1] recursive writing method, binary tree traversal, with recursion to write three traversal of the binary tree

The article directories

• • • Recursive three elements
    • Recursive practice, sequential traversal
    • 144. Antecedent traversal of binary trees
    • • Problem description
      • Solution 1 (Pre-ordered recursion, the time and space complexity is the same in both ways)
      • Solution 2 (Sequential iteration, time and space complexity is the same in both ways)
      • Solution 3 (Pre-order traversal, pop middle elements first, push two children, right child first, then left child)
      • Solution 4 (Sequential iteration, unified template)
    • Middle order traversal of binary trees
    • • Problem description
      • Solution 1 (Mid-order recursion, the time and space complexity is the same in both ways)
      • Solution 2+ Solution 3 (mid-order iteration, the time and space complexity of both approaches is the same)
      • Solution 4 (Mid-order iteration, unified template)
    • 145. Back-order traversal of binary trees
    • • Problem description
      • Solution 1 (Post-sequential recursion, the time and space complexity is the same in both ways)
      • Solution 2 (sequential iteration, time and space complexity of both methods are the same, omitted)
      • Solution 3 (backward traversal, third option of forward traversal, and then reverse)
      • Solution 4 (Post-sequence iteration, unified template)

Recursive three elements

This time we are going to talk about recursion, why many students see recursion algorithm is “a look will, a write is useless”.

The main reason is that there is no system for recursion and no methodology. “Every time I write a recursive algorithm, I rely on metaphysics to write the code.” Whether the code can be compiled depends on luck.

Some students may feel that it is very simple, but in fact it is not. We need to determine the methodology through simple topics. With the methodology, we can deal with complex recursion later.

This is to help you identify the three elements of the recursive algorithm. “Every time you write a recursion, follow these three elements to write, to ensure that you write the correct recursive algorithm!”

1. “Determine the parameters and return values of a recursive function:” First, determine which parameters need to be processed in the recursive process, then add this parameter to the recursive function; Second, the return value of each recursion is clearly defined, and then determine the return type of recursive function.
2. “Recursive termination conditions were determined:” finished recursive algorithm, run time, often encounter stack overflow error, just can’t write written termination or termination condition is wrong, the operating system also USES a stack structure to save the information each layer recursion if recursive not terminated, the operating system’s memory stack inevitably will overflow.
3. “Determine the logic of a single layer of recursion:” Determine the information that needs to be processed for each layer of recursion, and here also call itself repeatedly to achieve the recursion process.

Recursive practice, sequential traversal

void traversal(TreeNode* cur, vector<int>& vec)
Copy the code

if (cur == NULL) return;
Copy the code

vec.push_back(cur->val); / / in the traversal (cur - > left, vec); / / left traversal (cur - > right, vec); / / rightCopy the code

144. Antecedent traversal of binary trees

Problem description

Solution 1 (Pre-ordered recursion, the time and space complexity is the same in both ways)

Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node is traversed exactly once.

Space complexity: O(n), is the stack overhead during recursion, O(logn) in the average case, O(n) in the worst case, tree chain-like, O(n).

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> list = new ArrayList<>();
      preorderTraversal(root,list);
      return list;
    }
    public void preorderTraversal(TreeNode root,List<Integer> list){
        if(null == root) return; Root.val root. Left root. Right (root.val); root.val (root.val); / / preorderTraversal (root) left, a list); / / left preorderTraversal (root. Right, a list); / / right}}Copy the code

Why not recurse directly with the given preorderTraversal(TreeNode root), because the parameters are not allowed and there is no list in the parameters of the given method, which is the variable that must be changed in a single recursion.

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(null == root) returnlist; Root.val root. Left root. Right (root.val); root.val (root.val); // Modify list preorderTraversal(root.left); List preorderTraversal(root.right); // Right modify listreturnlist; }}Copy the code

1. It is better to write this way, as long as a method, extract the list, as a class variable, recurse using the given method; 2, preorderTraversal(root.left); And written list = preorderTraversal (root. Left); Add (root.val) has already modified the class variable list in one-way recursion, so it doesn’t matter whether you receive the returned value or not. If you receive the class variable, you also modify the class variable list. If you don’t receive the class variable list, the list has already been modified. If (null == root) return list; Instead of if(null == root) return null; When the input is [], the former will return [] correctly, and the latter will return null, returning an error. If (null == root) return list; if(null == root) return list; If (null == root) return list; It only returns to recursive subcalls (although it doesn’t matter if the subcalls receive or not) and doesn’t jump out of the entire Solution method.

Solution 2 (Sequential iteration, time and space complexity is the same in both ways)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;

        TreeNode node = root;
        Stack<TreeNode> stack=new Stack<>();
        while(node! =null || ! Stack.isempty ()) {// This must be written as node! =null because node is the p pointer, which is constantly changing, and root is the head pointer, which is invariantwhile(node ! = null) {// This must be truewhile, notiflist.add(node.val); // Stack. Push (node); // Node = node.left; } // node = stack.pop(); // Void node==null; // Void node==null; // Void node==null; }returnlist; }}Copy the code

Solution 3 (Pre-order traversal, pop middle elements first, push two children, right child first, then left child)

Because it is a direct push of the two children, and then in the pop of the child, so push and pop children in the opposite order, first push the right child, then push the left child

 class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root! =null) stack.push(root);while(! stack.isEmpty()) { TreeNode node=stack.pop();if(null ! = node){ list.add(node.val); // Add one to the list, then push the right child, push the left child stack.push(node.right); stack.push(node.left); }}returnlist; }}Copy the code

Solution 4 (Sequential iteration, unified template)

 class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        if(root! =null) stack.push(root);while(! stack.isEmpty()){ TreeNode node=stack.peek(); // Use node instead of rootif(node! =null){ stack.pop(); // Pop first, push fourif(node.right! =null) stack.push(node.right);if(node.left! =null) stack.push(node.left); stack.push(node); Val stack.push(null); val stack.push(null); }else{ stack.pop(); node=stack.pop(); list.add(node.val); }}returnlist; }}Copy the code

Middle order traversal of binary trees

Problem description

Solution 1 (Mid-order recursion, the time and space complexity is the same in both ways)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> list = new ArrayList<>();
      inorderTraversal(root,list);
      returnlist; } public void inorderTraversal(TreeNode root,List<Integer> List){// TreeNode root,List<Integer> Listif (root==null) return; inorderTraversal(root.left,list); list.add(root.val); inorderTraversal(root.right,list); }}Copy the code

Can be changed to a method, better, as follows:

class Solution { List<Integer> list = new ArrayList<>(); Public List<Integer> inorderTraversal(TreeNode root) {// inorderTraversal(TreeNode root)if (root==null) return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        returnlist; }}Copy the code

Solution 2+ Solution 3 (mid-order iteration, the time and space complexity of both approaches is the same)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode node =root;
        while(null ! = node || ! stack.isEmpty()){while(null ! = node){ stack.push(node); node = node.left; } node = stack.pop(); list.add(node.val); node = node.right; }returnlist; }}Copy the code

Solution 4 (Mid-order iteration, unified template)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        if(root! =null) stack.push(root);while(! stack.isEmpty()){ TreeNode node=stack.peek(); // Use node instead of rootif(node! =null){ stack.pop(); // Pop first, push fourif(node.right! =null) stack.push(node.right); stack.push(node); Val stack.push(null); val stack.push(null);if(node.left! =null) stack.push(node.left); }else{ stack.pop(); node=stack.pop(); list.add(node.val); }}returnlist; }}Copy the code

145. Back-order traversal of binary trees

Problem description

Given a binary tree, return its backward traversal.

Example:

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

Solution 1 (Post-sequential recursion, the time and space complexity is the same in both ways)

class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); PostorderTraversal (root,list); // Traversal(root,list);returnlist; } public void postorderTraversal(TreeNode root,List List){// Traversal traversal (TreeNode root,List Listif (null == root) return; // null==root checks to prevent null Pointers before threereturn; PostorderTraversal (root.left,list); / / left postorderTraversal (root. Right, a list); / / right list. Add (root. Val); / /}}Copy the code

class Solution { List<Integer> list=new ArrayList<>(); Public list <Integer> postorderTraversal(TreeNode root) {if (null == root) returnlist; // null==root checks to prevent null Pointers before threereturn; PostorderTraversal (root.left); / / left postorderTraversal (root. Right); / / right list. Add (root. Val); / /returnlist; }}Copy the code

Solution 2 (sequential iteration, time and space complexity of both methods are the same, omitted)

We can also implement the recursive function of method 1 iteratively. The two methods are equivalent, but the difference is that the recursion implicitly maintains a stack, while we need to simulate the stack explicitly during iteration. The rest of the implementation and details are the same, please refer to the following code.

Time complexity: O(n), where nn is the number of nodes in the binary search tree. Each node is traversed exactly once.

Spatial complexity: O(n), is the overhead of explicit stack in the iterative process, O(logn) in the average case, O(n) in the worst-case tree chain-like, O(n).

Solution 3 (backward traversal, third option of forward traversal, and then reverse)

  class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root! =null) stack.push(root);while(! stack.isEmpty()) { TreeNode node=stack.pop();if(null ! = node){ list.add(node.val); // Add one to the list, then push the right child and the left child stack.push(Node.left); stack.push(node.right); // Collections.reverse(list); // Collections.reverse(list);returnlist; }}Copy the code

Solution 4 (Post-sequence iteration, unified template)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        if(root! =null) stack.push(root);while(! stack.isEmpty()){ TreeNode node=stack.peek(); // Use node instead of rootif(node! =null){ stack.pop(); stack.push(node); Val stack.push(null); val stack.push(null);if(node.right! =null) stack.push(node.right);if(node.left! =null) stack.push(node.left); }else{ stack.pop(); node=stack.pop(); list.add(node.val); }}returnlist; }}Copy the code