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

理论基础

满二叉树概念

完全二叉树概念

二叉搜索树概念

平衡二叉搜索树概念

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

二叉树遍历方式：前中后序遍历，层次遍历。

二叉树的代码定义

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、确定单层递归的逻辑。

如果是递归遍历的话，要素一，参数是根节点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(!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;
    }
}