我正在嘗試從 Leetcode https://leetcode.com/problems/count-good-nodes-in-binary-tree/解決這個問題
這是我的解決方案：我無法理解為什么這種遞回 root.left 節點的計數值在遍歷 root.right 時不成立。在我的理解中我是
- 檢查當前節點是否良好并更新計數和串列
- 遍歷左節點更新計數
- 上面的計數應該在遍歷右節點時進入右節點并更新計數值但它沒有發生
為什么這不起作用。我知道正確的解決方案只是無法真正理解遞回如何重置我的計數變數
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int goodNodes(TreeNode root) {
int count = 0;
List<Integer> list = new ArrayList<>();
TreeNode treeroot = root;
preorderGoodNodes(root,list,count,treeroot);
return count;
}
public void preorderGoodNodes(TreeNode root,List<Integer> list,int count,TreeNode treeroot)
{
if(root==null) // check if root is null
return;
// if current node is actual root of the tree then count since root is always good
//also add the root to the list
if(treeroot ==root)
{
count ;
list.add(root.val);
}
else
// if node is not the root then check if it is good or not by looking into the list
{
int flag = 0;
for(int x : list) //looking into the list
{
if(x>root.val)
{
flag = 1;
break;
}
}
if(flag==0) // if it is good count
count ;
list.add(root.val); // weather good or not add to the list
}
List<Integer> rightlist = new ArrayList<>(list);
// make a copy of the list to send to right node
//because count and list from left tree should not effect right tree
preorderGoodNodes(root.left,list,count,treeroot);
**// why does count reset after this line ??**
preorderGoodNodes(root.right,rightlist,count,treeroot);
}
}
uj5u.com熱心網友回復：
如果您需要“按參考傳遞”語意，您可以使用AtomicIntegeror int[]of size1而不是int.
uj5u.com熱心網友回復：
的遞回呼叫preorderGoodNodes不會看到引數count的更新：它基本上是一個區域變數。該值及其任何更改僅在當前方法呼叫期間有效，并且在將其值傳遞給遞回呼叫時不會進行更改。
但是該方法當前是void: 而不是傳遞count，而是回傳它：
// No count parameter, return type now int
public int preorderGoodNodes(TreeNode root,List<Integer> list,TreeNode treeroot) {
int count = 0;
// ...
count ;
// ...
count = preorderGoodNodes(root.left,list,treeroot);
count = preorderGoodNodes(root.right,rightlist,treeroot);
return count;
}
然后，在您的goodNodes方法中：
return preorderGoodNodes(root,list,treeroot);
uj5u.com熱心網友回復：
感謝所有的答案。每個答案都幫助我理解。我能夠了解到問題不是我對回避呼叫的理解，而是我是按值發送變數而不是按參考發送的事實。
當我將 int 轉換為 int[] 進行計數時，這段代碼對我有用。請記住，解決此問題的標準方法是回傳 int 而不是 void
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int goodNodes(TreeNode root) {
int[] count = new int[1];
count[0]=0;
List<Integer> list = new ArrayList<>();
list.add(root.val);
TreeNode treeroot = root;
preorderGoodNodes(root,list,count,treeroot);
return count[0];
}
public void preorderGoodNodes(TreeNode root,List<Integer> list,int[] count,TreeNode treeroot)
{
if(root==null) // check if root is null
return;
// if current node is actual root of the tree then count since root is always good
//also add the root to the list
if(treeroot ==root)
{
count[0] ;
list.add(root.val);
}
else
// if node is not the root then check if it is good or not by looking into the list
{
int flag = 0;
for(int x : list) //looking into the list
{
if(x>root.val)
{
flag = 1;
break;
}
}
if(flag==0) // if it is good count
count[0] ;
list.add(root.val); // weather good or not add to the list
}
List<Integer> rightlist = new ArrayList<>(list);
// make a copy of the list to send to right node
//because count and list from left tree should not effect right tree
preorderGoodNodes(root.left,list,count,treeroot);
preorderGoodNodes(root.right,rightlist,count,treeroot);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/470051.html
下一篇：遞回函式-階乘