美文网首页
LeetCode 二叉树的中序遍历(递归和非递归算法)

LeetCode 二叉树的中序遍历(递归和非递归算法)

作者: 透明的红萝卜123 | 来源:发表于2019-03-14 09:35 被阅读0次

    二叉树的中序遍历
    给定一个二叉树,返回它的中序 遍历。
    示例:

    输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]
    

    非递归(思路更清晰):

    /**
     * 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> inorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            if(root == null) return list;
            TreeNode cur = root;
            //将currentNode移动到最左边
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            while(!stack.isEmpty()){
                //根结点的访问条件是只要左子树访问完毕,就可以访问根结点(左节点为空或者左节点为上次访问节点)
                cur = stack.pop();
                list.add(cur.val);
                //切换到右子树
                cur = cur.right;
                //访问右子树的最左边
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
            }
            
            return list;
            
        }
       
    }
    

    非递归:

    \/**
     * 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> inorderTraversal(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            if(root == null) return list;
            TreeNode cur = root;
            while(cur != null || !stack.isEmpty()){
                if(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }else{
                    cur = stack.pop();
                    list.add(cur.val);
                    cur =cur.right;
                }
            }
            return list;
            
        }
       
    }
    

    递归:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        ArrayList<Integer> list = new ArrayList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
            if(root == null) return new ArrayList<>();
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
            return list;
        }
       
    }
    

    相关文章

      网友评论

          本文标题:LeetCode 二叉树的中序遍历(递归和非递归算法)

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