Java Solution using Morris Traversal


  • 0
    J
    /**
     * 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> ret =new ArrayList<>();
            morris(ret,root);
            return ret;
        }
        public void morris(List<Integer> ret, TreeNode root){
            if(root == null){
                return;
            }
            TreeNode cur =root;
            //TreeNode pre;
            while(cur != null){
                if(cur.left == null){
                    ret.add(cur.val);
                    cur = cur.right;
                }
                else
                {
                    TreeNode pre = cur.left;
                    while(pre.right!=null && pre.right !=cur){
                        pre = pre.right;
                    }
                    if(pre.right==null){
                        pre.right =cur;
                        cur =cur.left;
                    }
                    else
                    {
                        ret.add(cur.val);
                        cur =cur.right;
                    }
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.