二叉树的中序遍历和后序遍历的递归与非递归代码示例

简介: 二叉树的中序遍历和后序遍历的递归与非递归代码示例

以下是二叉树中序遍历和后序遍历的递归与非递归代码示例:

中序遍历:

递归实现:

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
   
        this.val = val;
    }
}

public class BinaryTreeTraversalExample {
   

    public static void inOrderTraversal(TreeNode root) {
   
        if (root == null) {
   
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }

    public static void main(String[] args) {
   
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 执行中序遍历
        inOrderTraversal(root);
    }
}
AI 代码解读

非递归实现(使用栈):

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
   
        this.val = val;
    }
}

public class BinaryTreeTraversalExample {
   

    public static void inOrderTraversalNonRecursive(TreeNode root) {
   
        if (root == null) {
   
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr!= null) {
   
            if (curr!= null) {
   
                stack.push(curr);
                curr = curr.left;
            } else {
   
                curr = stack.pop();
                System.out.print(curr.val + " ");
                curr = curr.right;
            }
        }
    }

    public static void main(String[] args) {
   
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 执行中序遍历
        inOrderTraversalNonRecursive(root);
    }
}
AI 代码解读

后序遍历:

递归实现:

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
   
        this.val = val;
    }
}

public class BinaryTreeTraversalExample {
   

    public static void postOrderTraversal(TreeNode root) {
   
        if (root == null) {
   
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }

    public static void main(String[] args) {
   
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 执行后序遍历
        postOrderTraversal(root);
    }
}
AI 代码解读

非递归实现(使用两个栈):

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
   
        this.val = val;
    }
}

public class BinaryTreeTraversalExample {
   

    public static void postOrderTraversalNonRecursive(TreeNode root) {
   
        if (root == null) {
   
            return;
        }

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        s1.push(root);

        while (!s1.isEmpty()) {
   
            TreeNode curr = s1.pop();
            s2.push(curr);

            if (curr.left!= null) {
   
                s1.push(curr.left);
            }
            if (curr.right!= null) {
   
                s1.push(curr.right);
            }
        }

        while (!s2.isEmpty()) {
   
            System.out.print(s2.pop().val + " ");
        }
    }

    public static void main(String[] args) {
   
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 执行后序遍历
        postOrderTraversalNonRecursive(root);
    }
}
AI 代码解读
目录
打赏
0
7
8
0
158
分享
相关文章
|
3月前
|
二叉树的先序遍历和后序遍历的区别
先序遍历和后序遍历在遍历顺序、应用场景、实现方式以及复杂度等方面都存在一定的区别,在实际应用中需要根据具体问题的需求来选择合适的遍历方式。
96 5
后序遍历的递归和非递归实现有何区别?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
146 56
|
4月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
34 0
递归与非递归实现二叉树的前中后序遍历!!
递归与非递归实现二叉树的前中后序遍历!!
60 0
【递归调用在二叉树中的应用】前序遍历、中序遍历、后序遍历、求二叉树叶子结点及复制二叉树的C语言实现
【递归调用在二叉树中的应用】前序遍历、中序遍历、后序遍历、求二叉树叶子结点及复制二叉树的C语言实现
171 0
【递归调用在二叉树中的应用】前序遍历、中序遍历、后序遍历、求二叉树叶子结点及复制二叉树的C语言实现
【C++】非递归实现二叉树的前中后序遍历
【C++】非递归实现二叉树的前中后序遍历
【C++】非递归实现二叉树的前中后序遍历
二叉树的四种遍历方式(前序遍历,中序遍历,后序遍历,层序遍历)C++语言
二叉树的四种遍历方式(前序遍历,中序遍历,后序遍历,层序遍历)C++语言
260 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等