代码随想录算法训练营第14天

今日任务

● 理论基础 ● 递归遍历
● 迭代遍历 ● 统一迭代

链接：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE (opens in a new tab)

理论基础

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。即，深度为k，有2^k-1个节点的二叉树。

完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

平衡二叉树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

递归遍历

在深度优先遍历中：前中后序遍历，指的就是中间节点的遍历顺序。

前序遍历

另外两种遍历只需调整递归逻辑的顺序即可。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        traversal(root, ans);
        return ans;
    }
 
    // 1.返回值
    public void traversal(TreeNode cur, List<Integer> ans) {
        // 2.终止条件
        if(cur == null) return;
        // 3.单层递归逻辑
        ans.add(cur.val);
        traversal(cur.left, ans);
        traversal(cur.right, ans);
    }
}

迭代遍历

使用栈

前序遍历

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。为什么要先加入右孩子，再加入左孩子呢？因为这样出栈的时候才是中左右的顺序。

中序遍历

与前序遍历有很大不同。只用栈无法实现，需要使用一个指针cur来指向当前节点，并决定下一个节点是谁。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur == null) {
                // 到底了，处理一下，然后往右看
                cur = stack.pop();
                ans.add(cur.val);
                cur = cur.right;
            }
            else {
                // 没到底，继续往左下看
                stack.push(cur);
                cur = cur.left;
            }
        }
        return ans;
    }
}

后序遍历

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        else return ans;
        while(!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            ans.add(tmp.val);
            if (tmp.left != null) stack.push(tmp.left);
            if (tmp.right != null) stack.push(tmp.right);
        }
        Collections.reverse(ans);
        return ans;
    }
}

统一迭代

迭代写法不一致的原因是，访问节点（遍历节点）和处理节点（将元素放进结果集）不一致。所以使用标记法进行区分。就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点，这样只有空节点弹出的时候，才将下一个节点放进结果集。

以下代码以中序遍历为例：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        else return ans;
        while(!stack.isEmpty()) {
            TreeNode tmp = stack.peek();
            if(tmp != null) {
                stack.pop();
                if(tmp.right != null) stack.push(tmp.right);  // 右
                stack.push(tmp);  stack.push(null);           // 中
                if(tmp.left != null) stack.push(tmp.left);    // 左
            }
            else {
                stack.pop();
                ans.add(stack.pop().val);
            }
        }
        return ans;
    }
}