【算法第十一天7.25】二叉树前、中、后递归、非递归遍历-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法第十一天7.25】二叉树前、中、后递归、非递归遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链接：力扣94-二叉树中序遍历

链接：力扣144-二叉树前序遍历

链接：力扣145-二叉树后序遍历

树的结构

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

================================================

链接：力扣94-二叉树中序遍历

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：中序遍历，左中右 处理，对root的处理就是加入到集合中

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> list){
        // 当前传入的root为null结束本方法的执行，继续下面方法的执行
        if(root == null) return;
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}

非递归

思路

1、终止条件：栈为空且 cur节点为空

2、如果左孩子一直不为空，则需要一直入栈

3、左孩子为空后，则开始pop节点（入集合），pop出的节点也要看其左孩子，所以cur要指向pop出的节点，继续判断其左孩子

class Solution {
    public List<Integer> inorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        TreeNode cur = root;
        // 这里除了判空，也有可能栈空了，但是右节点还没有处理（未入栈）
        while(!stack.isEmpty() || cur != null){
            // 如果左孩子一直存在，则要一路把左孩子都存进去，直到cur为空
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            // cur为空时，则说明左边已经循环到低了，可以开始pop并入集合
            // 也需要开始处理右节点，右节点处理也是要一路把左节点先存进去，重复上述步骤
            // 所以要将右节点命为cur，也就是要处理的节点
            }else{
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }
}

链接：力扣144-二叉树前序遍历

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：前序遍历，中左右 处理，对root的处理就是加入到集合中，对左右节点处理，就是不断递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

非递归

思路

1、先让root入栈，接着pop出来，定义为node，先把node.val添加到集合中，再去判断其是否有左右孩子，一定先右后左，出栈顺序相反

2、循环终止条件：栈为空则说明所有节点已经处理完毕

class Solution {
    public List<Integer> preorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        stack.push(root);
        // 这里除了判空，不需要其它条件，即使出栈空了，后面还会有节点push进去
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return res;
    }
}

链接：力扣145-二叉树后序遍历

递归

思路

1、确定返回值和方法参数：需要集合来存放树各节点的值，最后打印出来，所以需要一个list集合作为参数，不断迭代；除此之外不需要有返回值

2、确定终止条件：当前节点为空时，则需要结束本次方法调用（结束本次递归），用return

3、确定单次递归逻辑：后序遍历，左右中 处理，对**root（传入节点）**的处理就是加入到集合中，对左右节点处理，就是不断递归

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root,res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> list){
        if(root == null) return;
        postorder(root.left, list);
        postorder(root.right,list);
        list.add(root.val);
    }
}

非递归

思路

入栈顺序中、左、右；出栈顺序：中、右、左；翻转顺序：左、右、中文章来源地址https://www.toymoban.com/news/detail-608269.html

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        // 入栈顺序中、左、右；出栈顺序：中、右、左；翻转顺序：左、右、中
        Collections.reverse(res);
        return res;
    }
}