美文网首页程序员iOS Developer
二叉树的前序,中序,后序遍历的递归与非递归实现

二叉树的前序,中序,后序遍历的递归与非递归实现

作者: 不可思议的Mark | 来源:发表于2017-03-31 22:15 被阅读472次
    二叉树的遍历方式

    先序遍历(Pre-Order Traversal)
    指先访问根,然后访问子树的遍历方式
    中序遍历(In-Order Traversal)
    指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式
    后序遍历(Post-Order Traversal)
    指先访问子树,然后访问根的遍历方式

    递归实现

    递归遍历二叉树非常简单,这里不做赘述,先给出中序遍历的代码

    /**
     * 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> inorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            if(root != null) tra(root, ans);
            return ans;
        }
        
        private void tra(TreeNode node, List<Integer> ans){
            if(node.left != null) tra(node.left, ans);
            ans.add(node.val);
            if(node.right != null) tra(node.right, ans);
        }
    }
    

    先序遍历只需要将递归方法中的ans.add(node.val);放到最前面,后序遍历只需要将递归方法中的ans.add(node.val);放到最后面就行。

    非递归实现
    前序遍历
    /**
     * 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> preorderTraversal(TreeNode root) {
            //用来保存结果的ArrayList.
            List<Integer> ans = new ArrayList<>();
            //用来存储右边节点的栈
            Stack<TreeNode> rights = new Stack<>();
            //遍历到的当前的节点
            TreeNode node = root;
            while(node != null){
                //将当前节点的值先放入结果
                ans.add(node.val);
                //如果当前节点的右边子节点不为空,则将其压入栈
                if(node.right != null){
                    rights.add(node.right);
                }
                //将当前节点置为当前节点的左节点
                node = node.left;
                //此时若为空,则前一步作废,将当前节点置为之前压入栈的右边的节点
                if(node == null && !rights.isEmpty()){
                    node = rights.pop();
                }
            }
            return ans;
        }
    }
    
    中序遍历
    /**
     * 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> inorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode node = root;
            while(node != null || !stack.empty()){
                while(node != null){
                    stack.add(node);
                    node = node.left;
                }
                node = stack.pop();
                ans.add(node.val);
                node = node.right;
            }
            return ans;
        }
        
    }
    
    后序遍历
    /**
     * 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) {
           LinkedList<Integer> ans = new LinkedList<>();
           Stack<TreeNode> stack = new Stack<>();
           if(root == null) return ans;
           stack.add(root);
           while(!stack.empty()){
               TreeNode node = stack.pop();
               ans.addFirst(node.val);
               if(node.left != null) stack.add(node.left);
               if(node.right != null) stack.add(node.right);
           }
           return ans;
        }
    }
    

    相关文章

      网友评论

        本文标题:二叉树的前序,中序,后序遍历的递归与非递归实现

        本文链接:https://www.haomeiwen.com/subject/vylvottx.html