Iteration and recursion mixed java solution


  • 0
    R
    private List<Integer> nodes=new ArrayList<>();
    
    public List<Integer> inorderTraversal(TreeNode root) 
    {
       Deque<TreeNode> stack=new ArrayDeque<>();
       List<Integer> nodes = new ArrayList<>();
       helper(root,nodes,stack);
       
       return nodes;
    }
    
    private void helper(TreeNode root, List<Integer> nodes,Deque<TreeNode> stack)
    {
      if(root==null)
        return;
    
      stack.offer(root);
     
      while(root.left!=null)
      {
        root=root.left;
        stack.offer(root);
      }
      
       TreeNode p = stack.pollLast();
       root=p;
       nodes.add(root.val);
    
      while(root.right==null)
      {
        TreeNode r = stack.pollLast();
        if(r==null)
    	return;
        root=r;
        nodes.add(root.val);
     }
      helper(root.right,nodes,stack);
    }

Log in to reply
 

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