Leetcode – 树的遍历总结（java）

蔚落 2022-08-10 09:40 102阅读 0赞

### 前序遍历 ###

前序二叉树遍历是树的经典面试题，解决这个问题的关键是要了解：1、什么是前序遍历（访问孩子前先访问父节点）？2、使用java核心库的Stack。对于一些奇怪的例子前序遍历不是很明显。但是如果使用栈来写这个程序，每个元素如何压入和弹出的就很明显了。解决这个问题的关键是使用栈来存储左右孩子，首先压入右孩子，这样就可以处理完左孩子后处理它。

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
     
    public class Solution {
        public ArrayList<Integer> preorderTraversal(TreeNode root) {
            ArrayList<Integer> returnList = new ArrayList<Integer>();
     
            if(root == null)
                return returnList;
     
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
     
            while(!stack.empty()){
            	
                TreeNode n = stack.pop();
                returnList.add(n.val);
     
                if(n.right != null){
                    stack.push(n.right);
                }
                if(n.left != null){
                    stack.push(n.left);
                }
     
            }
            return returnList;
        }
    }

### 中序遍历 ###

解决中序遍历的3个步骤：1、中序的顺序是左孩子->父节点-->右孩子；2、使用栈来记录节点；3、理解什么时候进栈和出栈

//定义一个二叉树
    public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }
     
    public class Solution {
        public ArrayList<Integer> inorderTraversal(TreeNode root) {
        	//注意要重置声明的数据元素，因为对于每一个测试用例都会使用同一个实例
             ArrayList<Integer> lst = new ArrayList<Integer>();
     
            if(root == null)
                return lst; 
     
            Stack<TreeNode> stack = new Stack<TreeNode>();
            //定义一个指针来跟踪节点
            TreeNode p = root;
     
            while(!stack.empty() || p != null){
     
                if(p != null){
                    stack.push(p);
                    p = p.left;
                }else{
                    TreeNode t = stack.pop();
                    lst.add(t.val);
                    p = t.right;
                }
            }
     
            return lst;
        }
    }

递归版：

public class Solution {
        List<Integer> result = new ArrayList<Integer>();
     
        public List<Integer> inorderTraversal(TreeNode root) {
            if(root !=null){
                helper(root);
            }
     
            return result;
        }
     
        public void helper(TreeNode p){
            if(p.left!=null)
                helper(p.left);
     
            result.add(p.val);
     
            if(p.right!=null)
                helper(p.right);
        }
    }

### 后续遍历 ###

在前序、中序和后续遍历问题中，后续遍历是最复杂的。解决后续遍历问题的步骤如下：1、后续遍历的顺序是左孩子->右孩子->父节点；2、找到先前访问节点和当前节点的关系；3、使用栈来跟踪节点。

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

### 层次遍历 ###

很明显要使用队列来解决这个问题，但是如果我们使用一个队列我们不能追踪每一层的开始，所以我们使用两个队列分别追踪当前层和下一层

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> nodeValues = new ArrayList<Integer>();
        if(root == null)
            return al;
     
        LinkedList<TreeNode> current = new LinkedList<TreeNode>();
        LinkedList<TreeNode> next = new LinkedList<TreeNode>();
        current.add(root);
     
        while(!current.isEmpty()){
            TreeNode node = current.remove();
     
            if(node.left != null)
                next.add(node.left);
            if(node.right != null)
                next.add(node.right);
     
            nodeValues.add(node.val);
            if(current.isEmpty()){
                current = next;
                next = new LinkedList<TreeNode>();
                al.add(nodeValues);
                nodeValues = new ArrayList();
            }
     
        }
        return al;
    }

参考：http://www.programcreek.com/2012/12/leetcode-solution-of-iterative-binary-tree-postorder-traversal-in-java/