Tree versions in Java: recursion, optimized tail recursion and pre-order iteration


  • 10
    K

    The most simple version is normal recursion:

    public class Solution {
    	public boolean isSymmetric(TreeNode root) {
    		return this.isMirror(root, root);
    	}
    
    	private boolean isMirror(TreeNode t0, TreeNode t1) {
    	if (t0 == null || t1 == null) {
    		return t0 == t1;
    	}
    	return t0.val == t1.val
    			&& this.isMirror(t0.left, t1.right)
    			&& this.isMirror(t0.right, t1.left);
    	}
    }
    

    And the last recursive call in method isMirror() above can be optimized to loop, this will reduce the actual recursive calls:

    public class Solution {
    	public boolean isSymmetric(TreeNode root) {
    		return this.isMirror(root, root);
    	}
    
    	private boolean isMirror(TreeNode t0, TreeNode t1) {
    		while (t0 != null && t1 != null) {
    			if (t0.val != t1.val || !this.isMirror(t0.left, t1.right)) {
    				return false;
    			}
    			t0 = t0.right;
    			t1 = t1.left;
    		}
    		return t0 == t1;
    	}
    }
    

    There are two kinds of iteration at least. The BFS-like iteration, which is based on queue, has a space complexity of O(n). And the DFS-like iteration, which is based on stack, has a better space complexity of O(log n).

    Here is the DFS-like pre-order iteration:

    public class Solution {
    	public boolean isSymmetric(TreeNode root) {
    		Deque<TreeNode[]> stack = new LinkedList<>();
    		stack.push(new TreeNode[]{root, root});
    		while (!stack.isEmpty()) {
    			TreeNode[] pair = stack.pop();
    			TreeNode t0 = pair[0], t1 = pair[1];
    			if (t0 == null && t1 == null) {
    				continue;
    			}
    			if (t0 == null || t1 == null || t0.val != t1.val) {
    				return false;
    			}
    			stack.push(new TreeNode[]{t0.left, t1.right});
    			stack.push(new TreeNode[]{t0.right, t1.left});
    		}
    		return true;
    	}
    }

  • 0
    K

    nicely done!


  • 0
    G

    I wonder how the dfs based solution is O(log n) space complexity. If you are using recursion based dfs(obviously not in this case), it should be O(h). In iteration based dfs, the only difference to bfs is a stack used instead of a queue, so it should be the same as that of BFS, which is O(n).


  • 0
    K

    “the only difference to bfs is a stack used instead of a queue, so it should be the same as that of BFS, which is O(n)”, I'm afraid I can't agree this with you. You know that recursive DFS is O(log n), and BFS is O(n). However, what iterative DFS does is just simulating recursive DFS with an explicit stack, so space complexity of iterative DFS should be the same as that of recusive DFS.


Log in to reply
 

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