二叉树算法题

• 103. 二叉树的锯齿形层序遍历
• 236. 二叉树的最近公共祖先

103. 二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

BFS遍历

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> res=new ArrayList<>();
        if(root==null){
            return res;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        boolean flag=true;

        while(!queue.isEmpty()){
            List<Integer> temp=new ArrayList<>();
            //注意在这里先计算size,
            //如果这么写：for(int i=0;i<queue.size();i++)
            //每次循环后queue的size会变化
            int count=queue.size();
            for(int i=0;i<count;i++){
                TreeNode node=queue.poll();
                if(flag){
                    temp.add(node.val);
                }else{
                    temp.add(0,node.val);
                }

                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(temp);
            flag=!flag;
        }
        return res;
    }
}
           

DFS遍历

这里要有个判断，如果走到下一层的时候集合没有创建，要先创建下一层的集合

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        dfs(root,res,0);
        return res;
    }

    public void dfs(TreeNode root,List<List<Integer>> res,int level){
        if(root==null){
            return;
        }
        if(res.size()<=level){
        //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
            List<Integer> newLevel=new ArrayList<>();
            res.add(newLevel);
        }
        //遍历到第几层我们就操作第几层的数据
        List<Integer> list=res.get(level);
        if(level%2==0){
            list.add(root.val);
        }else{
            list.add(0,root.val);
        }
        
        dfs(root.left,res,level+1);
        dfs(root.right,res,level+1);

    }
}
           

236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

236. 二叉树的最近公共祖先（DFS ，清晰图解）

C++ 经典递归】思路非常好理解 时间复杂度O(n), 空间复杂度O(n)

当我们用递归去做这个题时不要被题目误导，应该要明确一点

这个函数的功能有三个：给定两个节点 p 和 q

如果 p 和 q 都存在，则返回它们的公共祖先；

如果只存在一个，则返回存在的一个；

如果 p 和 q 都不存在，则返回NULL

本题保证给定的两个节点都存在，那自然还是能用上面的函数来解决

时间复杂度 O(N)： 其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。

空间复杂度 O(N) ： 最差情况下，递归深度达到 N ，系统使用 O(N)大小的额外空间。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        // p和q在两侧
        if(left!=null&&right!=null){
            return root;
        }
        return null; // 必须有返回值
        
    }
}