关于二叉树:二叉树中递归遇到的问题

本篇文章以求二叉树中的最大值和最小值的最大差值为例，记录一下递归中遇到的问题，是递归时的参数问题，什么时候须要把变量放在参数中，什么时候须要把变量定义为全局变量。

变量定义为全局变量

以上面的二叉树为例，求整棵树中的节点的值的最大差值，也就是求出最大值和最小值。

前序遍历的过程如下：

图中圆圈中记录的是结点的拜访程序，前序的遍历程序和拜访程序雷同。

走到结点 1（遍历结点），记录下以后的最大值和最小值 [1, 1]（拜访结点），而后遍历左子树，遍历完左子树再右子树。

当走到节点 2 时，更新最大值和最小值时，是和 [1, 1] 比拟的，所以记录的最大值和最小值是 [2, 1]。

当走到节点 4 时，更新最大值和最小值时，是和 [2, 1] 比拟的，所以记录的最大值和最小值是 [4, 1]。

当走到节点 5 时，更新最大值和最小值时，是和 [4, 1] 比拟的，所以记录的最大值和最小值是 [5, 1]。

当走到节点 3 时，更新最大值和最小值时，是和 [5, 1] 比拟的，所以记录的最大值和最小值是 [5, 1]。

当走到节点 6 时，更新最大值和最小值时，是和 [5, 1] 比拟的，所以记录的最大值和最小值是 [6, 1]。

遍历完之后，从节点 4 回到 节点 2 的时候（回溯的时候），最大值和最小值也回到节点 2 时的值 [2, 1]。所以当遍历的门路从 1-2-4 走到 1-2-5 时，节点 5 更新最大值和最小值时，是和 [2, 1] 比拟的，而不是 [4, 1]。

上面的代码是求二叉树中最大差值，代码应用 java 实现前序遍历。因为最大值和最小值是在整个遍历过程中对所有节点都是可见的（每次比拟的是同一个最大值和最小值），节点会回退，而变量值是不回退的（回溯）。

int diff = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

public void getMaxDifference(TreeNode root) {if (root == null) return;
    
    // 更新最大值、最小值和差值
    if (root.val > max) max = root.val;
    if (root.val < min) min = root.val;
       if (max - min > diff) diff = max - min;  
    getMaxDifference(root.left);
    getMaxDifference(root.right);
}

变量作为办法参数

如果是求二叉树中所有门路上的差值的最大（每条门路上都有一个最大值和最小值的差值，求所有门路中的差值中的最大值）。应该怎么求呢？？

上面的图中是前序遍历的过程。和上背后序遍历过程不同的是，这次每个节点中更新最大值和最小值时，比拟的值是该条门路上的最大值和最小值，而不是二叉树中所有节点中的最大值和最小值。

图中，[最大值，最小值] 记录的拜访以后节点时的最大值和最小值，绿色线是从上到下遍历时走的路线，红色线是节点回退时走的路线。

当走到节点 4 时，记录的最大值和最小值是 [4, 1]。遍历完之后，从节点 4 回到 节点 2 的时候（回溯的时候），最大值和最小值也回到节点 2 时的值 [2, 1]。所以当遍历的门路从 1-2-4 走到 1-2-5 时，节点 5 更新最大值和最小值时，是和 [2, 1] 比拟的，而不是 [4, 1]。

同理，节点 3 更新最大值和最小值时，是和 [1, 1] 比拟的，而不是 [5, 1]，所以它记录的值是 [3, 1]。

节点 6 更新最大值和最小值时，是和 [3, 1] 比拟的，所以它记录的值是 [6, 1]。

从遍历的过程中，发现更新最大值和最值时比拟的值并不是全局中求得的最大值和最小值，因为最大值和最小值并不是全局的而是在遍历完之后就会隐没，所以，须要批改下面的代码

int diff = 0;  // 差值
public void getMaxDifference(TreeNode root, int max, int min) {
    // 遍历到空节点，一条门路走完，记录这条门路的后果
    if (root == null){if (max - min > diff) diff = max - min;  // 更新差值
        return;
    } 
    
    // 更新最大值、最小值（它们的值只作用于此次递归，递归完结后就隐没）if (root.val > max) max = root.val;
    if (root.val < min) min = root.val;
    getMaxDifference(root.left, max, min);
    getMaxDifference(root.right, max, min);
}

递归时栈中元素变动

在递归时，每一次递归会把本次递归的局部变量等压入栈中，在递归完结后会把局部变量再弹出栈，所以递归完结后，是没有值的。递归两头的值是不保留的。

所以，前序遍历过程中栈中元素的变动如下：

另外要说的一点是，根本类型作为办法参数，在办法内扭转参数的值，是不能影响办法外的值的。参数的作用范畴只在办法内。所以上面的代码是有效的

// 替换两个整数
public void swap(int a, int b) {
    int t = a;
    a = b;
    b = t;
}

public void test() {
    int a = 3, b = 4;
    swap(a, b);
    // a 还是 3, b 还是 4，并不是真的产生替换
}