java - 递归程序中类变量到方法参数的转换

Question

我已经解决了 leetcode 问题找到 Sum of left leaves在具有此代码的树中。我知道在递归中使用类变量作为临时变量不是一个好的做法，并且知道如何将临时结果作为方法参数传递。在这种情况下，我想避免使用类变量 sum 并使辅助方法 sumOfLeftLeaves(TreeNode root,TreeNode parent,int sum) 带有附加参数。请建议我如何修改方法。我尝试了不同的方法来做到这一点，但对返回值感到震惊。

//Find sum of all left nodes in a binary tree.    
public class Solution {
        //Class variable to capture sum
        int sum = 0;
        public int sumOfLeftLeaves(TreeNode root) {
             sumOfLeftLeaves(root,null);
             return sum;
        }

        public void sumOfLeftLeaves(TreeNode root,TreeNode parent){
            if(root != null){
                sumOfLeftLeaves(root.left,root);
                //If the node is a leaft node and it is left node to the parent
                if(root.left == null && root.right == null && (parent != null && parent.left == root)){
                    sum += root.val;
                }
                sumOfLeftLeaves(root.right,root);
            }
        }
    }

Answer 1

总是根据自身的更简单版本来定义递归问题。

调用函数 LL。

基本情况:LL(空) ≡ 0, LL(左叶节点) ≡ node.val, LL(右叶节点) ≡ 0

归纳案例:给定 LL( node.left ) 和 LL( node.right ) -> LL( node ) ≡ LL( node.left ) + LL( node.right )

public int sumOfLeftLeavesAux( TreeNode node, boolean flgIsLeftChild ) {
    // base case: empty tree
    if ( node == null )
        return 0;
    // base case: leaf node
    if ( node.left == null && node.right == null )
        return flgIsLeftChild ? node.val : 0;
    // inductive case
    return sumOfLeftLeavesAux( node.left, true ) + sumOfLeftLeavesAux( node.right, false );
}