Java 二叉树的遍历实现

深碍√TFBOYSˉ_ 2022-05-22 10:35 134阅读 0赞

**前序遍历**：先访问根节点，再访问左子节点，最后访问右子节点（根左右）

**中序遍历**：先访问左子节点，再访问根节点，最后访问右子节点（左根右）

**后序遍历**：先访问左子节点，再访问右子节点，最后访问根节点（左右根）

这三种遍历都有递归和循环两种实现方法，每种遍历的递归实现都比循环实现要简洁的多。

leetcode练习地址：

[二叉树的前序遍历    ][Link 1]

[二叉树的中序遍历][Link 2]

[二叉树的后序遍历][Link 3]

前序遍历的递归方法：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            printOne(root, result);
            return result;
        }
    
        private void printOne(TreeNode root,List<Integer> result){
            if(root != null){
                result.add(root.val);
                printOne(root.left, result);
                printOne(root.right, result);
            }
        }
    }

前序遍历的循环方法（迭代方法，用栈放右子节点）：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            while(root != null){
                result.add(root.val);
                if(root.right != null){
                    stack.push(root.right);
                }
                root = root.left;
                if(root == null && !stack.isEmpty()){
                    root = stack.pop();
                }
            }
            return result;
        }
    }

中序遍历和后序遍历的递归只需修改三个节点的执行顺序就可以了

中序改为

printOne(root.left, result);
    result.add(root.val);
    printOne(root.right, result);

后序改为

printOne(root.left, result);
    printOne(root.right, result);
    result.add(root.val);

中序迭代方法

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode node = stack.pop();
                result.add(node.val); 
                p = node.right;   
            }
        }
        return result;
    }

后序迭代方法

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode p = root;
        while(!stack.isEmpty() || p != null) {
            if(p != null) {
                stack.push(p);
                result.addFirst(p.val); 
                p = p.right;           
            } else {
                TreeNode node = stack.pop();
                p = node.left;     
            }
        }
        return result;
    }

[Link 1]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
[Link 2]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
[Link 3]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/