1.二叉树的中序遍历
给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
示例一:
示例二:
示例三:
1.递归求解
所谓中序遍历就是先访问左子树,再遍历根节点,最后访问右子树。
下图是中序遍历一个二叉树的动态演示过程,
最后遍历出的结果为8,11,12,20,22,29,32,41,46,50,51,65,72,91,99;
由于中序遍历的定义就是一个递归的过程,在这里我们可以直接采用递归的方式求解遍历!具体代码如下所示:
/**
* 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) {
List<Integer> res=new ArrayList<>();
accessTree(root,res);
return res;
}
//二叉树的中序遍历
public void accessTree(TreeNode root,List<Integer> res){
if(root==null){
return ;
}
accessTree(root.left,res);
res.add(root.val);
accessTree(root.right,res);
}
}
2.时间复杂度分析
在时间上,我们对二叉树进行了一次遍历,因此时间复杂度为 O ( n ) O(n) O(n);
空间上,我们使用ArrayList集合来存储遍历出的节点,因此空间复杂度为 O ( n ) O(n) O(n);
该代码在LeetCode中的执行情况如下所示:
3.循环迭代求解
前面我们使用了递归的方式进行求解,但是在真实的面试过程中,面试官一般除了要求你写出递归的求解方式外,还会要求你写出循环迭代的求解方式。
方法一的递归函数我们也可以用迭代的方式实现,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其他都相同,具体实现可以看下面的代码。
/**
* 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) {
List<Integer> res=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root=root.left;
}
root=stack.pop();
res.add(root.val);
root=root.right;
}
return res;
}
}
4.GIF动图演示
以二叉树A(B(,D),C(,E)为例,上述代码的具体演示
5.时间复杂度分析
从时间上,循环迭代仍然是对二号数中的每一个节点遍历一次,因此时间复杂度为 O ( n ) O(n) O(n);
从空间上,循环迭代使用了栈来模拟迭代过程,使用ArrayList集合在存储当前中序遍历所遍历的节点!具体代码在LeetCode中的执行情况如下所示: