如何在这个递归方法中只使用一个返回值。

huangapple go评论73阅读模式
英文:

how to use only 1 return in this recursive method

问题

// 有多少个节点恰好有一个非空子节点
public int stickCt() { 
    return stickCt(root);
}

private int stickCt(StringNode t) { 
    int count = 0;
    if (t == null)
        return 0;

    else if ((t.getLeft() == null && t.getRight() != null) || (t.getLeft() != null && t.getRight() == null))
        count++;

    count = count + stickCt(t.getLeft()) + stickCt(t.getRight());
    return count;
}
英文:

I'm finishing up the easy portion project and my professor specified that he only wants methods with at maximum 1 return. I can't seem to figure out how to make this work correctly with only 1 return though. For context, I am finding how many nodes in a tree have exactly 1 non-null children.

// How many nodes have exactly 1 non-null children
	public int stickCt() { 
		return stickCt(root);
	}
	private int stickCt(StringNode t) { 
		int count = 0;
		if (t == null)
			return 0;
		
		else if ((t.getLeft() == null && t.getRight() != null) || (t.getLeft() != null & t.getRight() == null))
			count++;
		
		count = count + stickCt(t.getLeft()) + stickCt(t.getRight());
		return count;
		
	}

答案1

得分: 1

以下是翻译好的部分:

private int stickCt(StringNode t) { 
    int count = 0;
    if (t != null) {
        if ((t.getLeft() == null && t.getRight() != null) || (t.getLeft() != null && t.getRight() == null))
            count++;
        count += stickCt(t.getLeft()) + stickCt(t.getRight());
    }
    return count;
}

然而在这种情况下我发现您使用两个返回语句的表述更容易理解
英文:

Something like this:

private int stickCt(StringNode t) { 
    int count = 0;
    if (t != null) {
        if ((t.getLeft() == null && t.getRight() != null) || (t.getLeft() != null & t.getRight() == null))
            count++;
        count += stickCt(t.getLeft()) + stickCt(t.getRight());
    }
    return count;
}

However, in this case I find your formulation with the 2 returns easier to understand.

答案2

得分: 0

使用递归算法的替代方法是使用广度优先搜索(BFS)或深度优先搜索(DFS)算法。

以下是一个BFS方法的示例:

public int stickCt(StringNode root){
    int count = 0;

    Queue<StringNode> queue = new LinkedList<StringNode>();
    queue.add(root);

    while (!queue.isEmpty()){ 
        StringNode tempNode = queue.poll();

        if (tempNode != null && (tempNode.getLeft() == null && tempNode.getRight() != null) || (tempNode.getLeft() != null && tempNode.getRight() == null)){
            count++;
        }

        /*将左子节点入队*/
        if (tempNode.getLeft() != null) { 
            queue.add(tempNode.getLeft()); 
        } 

        /*将右子节点入队*/
        if (tempNode.getRight() != null) { 
            queue.add(tempNode.getRight()); 
        }
    }

    return count; 
}

注意:由于您请求只返回翻译的部分,我已经将代码部分翻译为中文。如果您有任何其他问题或需要进一步帮助,请随时提问。

英文:

Instead using recursive algorithm you can use BFS of DFS algorithm.

Here is an example or BSF approach

public int stickCt(StringNode root){
        int count = 0;

        Queue&lt;StringNode &gt; queue = new LinkedList&lt;StringNode &gt;();
        queue.add(root);

        while (!queue.isEmpty()){ 
            StringNode tempNode = queue.poll();

            if (tempNode != null &amp;&amp; (tempNode.getLeft() == null &amp;&amp; tempNode.getRight() != null) || (tempNode.getLeft() != null &amp;&amp; tempNode.getRight() == null)){
                count++;
            }
           
            /*Enqueue left child */
            if (tempNode.getLeft()!= null) { 
                queue.add(tempNode.getLeft()); 
            } 
  
            /*Enqueue right child */
            if (tempNode.getRight()!= null) { 
                queue.add(tempNode.getRight()); 
            }
        }
    
        return count; 
    }

huangapple
  • 本文由 发表于 2020年10月11日 16:06:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/64301848.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定