LeetCode:94 & 145 & 144

Posted on

递归

94.Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null) {return new ArrayList<>();}
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, List<Integer> res){
        if(root==null) {return;}
        helper(root.left,res);
        res.add(root.val);
        helper(root.right,res);
    }
}

144.Binary Tree Preorder Traversal

1
2
3
4
5
6
public static void helper(TreeNode root, List<Integer> res) {
        if(root==null) {return;}
        res.add(root.val);
        helper(root.left,res);
        helper(root.right,res);
    }

145.Binary Tree Postorder Traversal

1
2
3
4
5
6
public static void helper(TreeNode root, List<Integer> res) {
        if(root==null) {return;}
        helper(root.left,res);
        helper(root.right,res);
        res.add(root.val);
    }

递归方法只需要根据要求改变递归的顺序即可，当递归执行到空节点时返回即可，res.add()保证了每次递归都会添加当前节点，通过调整位置来实现不同序的遍历。

复杂度分析

  • 时间复杂度：O(n)。递归函数 T(n) = 2T(n/2)+1。
  • 空间复杂度：最坏情况下需要空间O(n)，平均情况为O(logn)。