java 谁能解释二叉树遍历的递归代码?

nxagd54h  于 2023-02-02  发布在  Java
关注(0)|答案(1)|浏览(115)

使用递归的二叉树中序遍历。
谁能解释一下这些递归调用是如何工作的。

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> inorder=new ArrayList<>();
        result(root,inorder);
        return inorder;
    }
    void result(TreeNode root,ArrayList<Integer> inorder){
        if (root==null){
            return ;
        }
        result(root.left,inorder);
        inorder.add(root.val);
        result(root.right,inorder);
    }
}

我无法理解递归是如何工作的。

ftf50wuq

ftf50wuq1#

试着把它画在纸上。基本上是这样的:对于每个节点,您将左子树的所有节点添加到列表中,然后是该节点,然后是右子树的所有节点。如果节点的排序方式是左节点的值都比形成(子)树根的节点小,右节点的值都比该节点大,则列表将被排序。
我来举个例子。
让我们假设下面的树:

5
     /      \
    3        7
   / \      / \
  1   4    6   8
   \            \  
    2            9

现在遍历从根(5)开始并执行以下操作:

  • 向左转到3(递归调用#1)
  • 向左转到1(递归调用#2)
  • 加1
  • 从1向右到2(递归调用#3)
  • 加2
  • 返回到1(调用#3返回)
  • 返回到3(调用#2返回)
  • 加3
  • 向右转到4(递归调用#4)
  • 加4
  • 返回到3(调用#4返回)
  • 返回5(呼叫#1返回)
  • 加5
  • 向右转到7(递归调用#5)
  • ......(剩下的我让你来安排)

相关问题