Is my method a recursive one? Java Solution


  • 0
    S

    I use two recursive traversal on tree.

    one is right-left-middle. (preorder)

    another is left-right-middle. (postorder)

    and then use two lists to carry the path, and then compare the two lists.

    (P.S. The preorder is not real preorder traversal, I named it here as an opposite traversal versa postorder.)

    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            List<TreeNode> preorder = new ArrayList<TreeNode>();
            List<TreeNode> postorder = new ArrayList<TreeNode>();
            traversal_preorder(root, preorder);
            traversal_postorder(root, postorder);
            for(int i = 0;i < preorder.size() && i < postorder.size();i++){
                if(preorder.get(i)==null && postorder.get(i)==null)
                    continue;
                if(preorder.get(i)==null || postorder.get(i)==null)
                    return false;
                if(preorder.get(i).val!=postorder.get(i).val)
                    return false;
            }
            return preorder.size()==postorder.size();
        }
        
        private void traversal_preorder(TreeNode root, List<TreeNode> list){
            if(root==null){return;}
            if(root.left==null)
                list.add(null);
            else
                traversal_preorder(root.left,list);
            
            if(root.right==null)
                list.add(null);
            else
                traversal_preorder(root.right,list);
            list.add(root);
        }
        
        private void traversal_postorder(TreeNode root, List<TreeNode> list){
            if(root==null){return;}
            if(root.right==null)
                list.add(null);
            else
                traversal_postorder(root.right,list);
            
            if(root.left==null)
                list.add(null);
            else
                traversal_postorder(root.left,list);
            list.add(root);
        }
    }

Log in to reply
 

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