Sequence traversal of binary tree ii[one of sequence traversal methods - > recursive traversal + level]

Preface

Hierarchical traversal is the basis of the operation tree , Hierarchical traversal is a variation of hierarchical traversal , General available queues + layer size To stratify , You can also recursively traverse +level To stratify . Through zigzag hierarchical traversal binary tree to practice the previous traversal +level To stratify .

One 、 Sequence traversal of binary tree II

Two 、 Recursive traversal + level layered

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    
        //  The former sequence traversal  + level  Implement hierarchical traversal .
        List<List<Integer>> ans = new ArrayList<>();
        preOrder(root, ans, 0);
        return ans;
    }
    private void preOrder(TreeNode root, List<List<Integer>> ans, int level) {
    
        // null node , Recursive termination .
        if (root == null) return;
        //  Going down one layer at a time , So choose to wait .
        if (level == ans.size()) ans.add(0,new ArrayList<>());
        List<Integer> cur = ans.get(ans.size() - 1 - level);
        cur.add(root.val);
        //  The former sequence traversal 
        preOrder(root.left, ans, level + 1);
        preOrder(root.right, ans, level + 1);
    }
    
}

summary

1） Level traversal , Hierarchical traversal .
2） queue + layer size layered | Recursive traversal + level layered .

reference

[1] LeetCode Sequence traversal of binary tree II