代码随想录算法训练营第十四天|理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代

理论基础

满二叉树概念

二叉树的概念是完整的

二叉搜索树的概念

平衡二叉搜索树的概念

二叉树的存储方式：链式存储和顺序存储

二叉树遍历：前、中、后顺序遍历，层次遍历。

二叉树的代码定义

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;  }}

二叉树递归遍历

确定递归三要素：

1、确定递归函数的参数和返回值

2、确定终止条件

3、确定单层递归的逻辑。

如果是递归遍历，元素1，参数是根节点root，返回值是数组res；元素二，挡遍历的节点为空，递归结束；元素三，单层递归是判断中左右，还是左中右，还是左中右。

非递归遍历法，借用栈结构，如为前序，中-左-右，入栈顺序为中-右-左；中序，左-中-右，入栈为左-右，不断遍历，直至节点为空；

后续是左右中，入栈，中左右，出栈中右左，最后翻转。

相当于暂时不处理中间节点。中间节点进入堆栈后，再添加null节点，以便一旦出堆栈遇到null，就可以处理中间节点。

//后序->左右中， 入栈->中右左class Solution {    public List<Integer> postorderTraversal(TreeNode root) {        List<Integer> res = new ArrayList<>();        Deque<TreeNode> deq = new LinkedList<>();        if(root != null) deq.push(root);        while(!= null) deq.push(root);        while(!deq.isEmpty()){            TreeNode node = deq.peek();            if(node != null){                deq.poll();                //左右中                deq.push(node);                deq.push(null);                if(node.right != null) deq.push(node.right);                if(node.left != null) deq.push(node.left);            }else{                deq.pop();                node = deq.peek();                deq.pop();                res.add(node.val);            }        }        return res;    }}