使用递归的二叉树中序遍历。
谁能解释一下这些递归调用是如何工作的。
/**
* 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);
}
}
我无法理解递归是如何工作的。
1条答案
按热度按时间ftf50wuq1#
试着把它画在纸上。基本上是这样的:对于每个节点,您将左子树的所有节点添加到列表中,然后是该节点,然后是右子树的所有节点。如果节点的排序方式是左节点的值都比形成(子)树根的节点小,右节点的值都比该节点大,则列表将被排序。
我来举个例子。
让我们假设下面的树:
现在遍历从根(5)开始并执行以下操作: