Postorder traversal solution


  • 0
    J

    Yet another solution, that traverse the tree in postorder manner.

    public class Solution {
        
        private TreeNode lca;
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p == null || q == null) {
                return null;
            }
    
            dfs(root, p, q);
            return lca;
        }
        
        private int dfs(TreeNode node, TreeNode p, TreeNode q) {
    
            if(node == null) {
                return 0;
            }
            
            final int left = dfs(node.left, p, q);
            final int right = dfs(node.right, p, q);
    
            int curr = 0;
            if(node == p || node == q) {
                curr = 1;
            }
            
            if(curr + left + right == 2 && lca == null) {
                lca = node;
            }
            
            return curr + left + right;
        }
    }

  • 1
    G

    isn't this preorder? You check the current node first, then left node and right node.


  • 0
    J

    I have made the code more clear to point that it's in fact postorder.


Log in to reply
 

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