二叉樹算法題

• 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; // 必須有傳回值
        
    }
}