《算法文章匯總》

單鏈表有多個(gè)next指針就變成樹了。

Linked List是特殊化的Tree,Tree是特殊化的Graph。
沒有環(huán)的圖就是樹。

樹節(jié)點(diǎn)

Java
public class TreeNode{
     public int val;
     public TreeNode left,right;
     public TreeNode(int val){
         this.val = val;
         this.left = null;
         this.right = null;
     }
}

C++
struct TreeNode{
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x):val(x),left(NULL),right(NULL){}
}

二叉樹遍歷

1.前序:根-左-右
2.中序:左-根-右
3.后序:左-右-根
遍歷基本上基于遞歸的

def preorder(self,root):
if root:
self traverse_path append(root val)
self preorder(root left)
self preorder(root right)

def inorder(self,root):
if root:
   self inorder(root left)
   self traverse_path append(root val)
   self inorder(root right)
   
   
def postorder(self,root)
if root:
   self postorder(root left)
   self postorder(root right)
   self traverse_path append(root val)

二叉搜索樹Binary Search Tree

二叉搜索樹，也稱二叉排序樹、有序二叉樹、排序二叉樹，是指一棵空樹或者具有下列性質(zhì)的二叉樹:

1.左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
2.右子樹上的所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
3.依次類推:左、右子樹也分別為二叉查找樹。(這就是重復(fù)性！)
中序遍歷:升序遍歷
1.查詢 log2(n)
2.插入新節(jié)點(diǎn)(創(chuàng)建) log2(n)
3.刪除

二叉樹的中序遍歷

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
給定一個(gè)二叉樹，返回它的中序遍歷。
輸入: [1,null,2,3]
1

2
/
3
輸出: [1,3,2]

方法一:遞歸法

第一種解決方法是使用遞歸。這是經(jīng)典的方法，直截了當(dāng)。我們可以定義一個(gè)輔助函數(shù)來實(shí)現(xiàn)遞歸。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
    }
}

public class Solution {
    
    @Test
    public void testBinaryTree(){
        TreeNode root = new TreeNode(1);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree5 = new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree6 = new TreeNode(6);
        root.left = tree2;
        root.right = tree3;
        tree2.left = tree4;
        tree2.right = tree5;
        tree3.left = tree6;

        List<Integer> res = inorderTraversal(root);
        System.out.printf(res.toString());
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        helper(root,res);
        return res;
    }

    public void helper(TreeNode root,ArrayList<Integer> res){
        if(root != null){
            if(root.left != null){
                helper(root.left,res);
            }
            res.add(root.val);
            if(root.right != null){
                helper(root.right,res);
            }
        }
    }
}
//輸出
[4, 2, 5, 1, 6, 3]

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)。遞歸函數(shù) T(n) = 2 * T(n/2)+1。
空間復(fù)雜度：最壞情況下需要空間O(n)O(n)，平均情況為O(\log n)O(logn)。

二叉樹.png

方法二:基于棧的遍歷

public class Solution {
    @Test
    public void testStack(){
        TreeNode root = new TreeNode(1);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree5 = new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree6 = new TreeNode(6);
        root.left = tree2;
        root.right = tree3;
        tree2.left = tree4;
        tree2.right = tree5;
        tree3.left = tree6;

        List<Integer> res = inorderTraversal0(root);
        System.out.printf(res.toString());
    }

    public List<Integer> inorderTraversal0(TreeNode root){
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()){
            while(curr != null){
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
」
//輸出
[4, 2, 5, 1, 6, 3]

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)O(n)。

空間復(fù)雜度：O(n)O(n)。

二叉樹的前序遍歷

方法一:遞歸法

class Solution {
    @Test
    public void testpreorderTravelsal(){
        TreeNode root = new TreeNode(1);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree5 = new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree6 = new TreeNode(6);
        root.left = tree2;
        root.right = tree3;
        tree2.left = tree4;
        tree2.right = tree5;
        tree3.left = tree6;

        List<Integer> res = preorderTraversal(root);
        System.out.printf(res.toString());
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        helper0(root,res);
        return res;
    }

    public void helper0(TreeNode root,ArrayList<Integer> res){
           if(root != null){
               res.add(root.val);
               if(root.left!=null){
                   helper0(root.left,res);
               }
               if(root.right!=null){
                   helper0(root.right,res);
               }
           }
    }
}
//輸出
[1, 2, 4, 5, 3, 6]

方法二:基于棧的遍歷

@Test
    public void testPreorderTraversalStack0(){
        TreeNode root = new TreeNode(1);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree5 = new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        TreeNode tree3 = new TreeNode(3);
        TreeNode tree6 = new TreeNode(6);
        root.left = tree2;
        root.right = tree3;
        tree2.left = tree4;
        tree2.right = tree5;
        tree3.left = tree6;

        List<Integer> res = preorderTraversal0(root);
        System.out.printf(res.toString());
    }

    public List<Integer> preorderTraversal0(TreeNode root){
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curr = root;
        while(curr != null || !stack.isEmpty()){
            while(curr!= null){
                res.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            curr = curr.right;
        }
        return res;
    }
//輸出
[1, 2, 4, 5, 3, 6]
時(shí)間復(fù)雜度：訪問每個(gè)節(jié)點(diǎn)恰好一次，時(shí)間復(fù)雜度為 O(N)O(N) ，其中 NN 是節(jié)點(diǎn)的個(gè)數(shù)，也就是樹的大小。
空間復(fù)雜度：取決于樹的結(jié)構(gòu)，最壞情況存儲(chǔ)整棵樹，因此空間復(fù)雜度是 O(N)O(N)。

N叉樹的前序遍歷

@Test
    public void testPreOrder(){
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        ArrayList<Node> list = new ArrayList<Node>();
        list.add(node3);
        list.add(node2);
        list.add(node4);
        root.children = list;
        ArrayList<Node> list0 = new ArrayList<Node>();
        list.add(node5);
        list.add(node6);
        node3.children = list0;
        List<Integer> list1 = preorder(root);
        System.out.println(list1.toString());
    }

    public List<Integer> preorder(Node root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Node curr = root;
        helper(curr,res);
        return res;
    }
    public void helper(Node curr,ArrayList<Integer> res){
        if(curr != null){
            res.add(curr.val);
            if(curr.children != null && curr.children.size()>0){
                for(Node node:curr.children){
                    helper(node,res);
                }
            }
        }
    }
//輸出
[1, 3, 2, 4, 5, 6]

二叉樹的后序遍歷

方法一:遞歸法

         //后序遍歷postorder traversal
         public List<Integer> postorderTraversal(TreeNode root) {
             ArrayList<Integer> res = new ArrayList<>();
             helper0(root,res);
             return res;
         }
         //遞歸
         void helper0(TreeNode node,ArrayList<Integer> res){
             if (node!=null){
                 if (node.left!=null){
                     helper0(node.left,res);
                 }
                 if (node.right!=null){
                     helper0(node.right,res);
                 }
                 res.add(node.val);
             }
         }

方法二:棧

         //棧
         public List<Integer> postorderTraversal0(TreeNode root) {
             ArrayList<Integer> res = new ArrayList<>();
             Stack<TreeNode> stack = new Stack<>();
             TreeNode cur = root;
             while (!stack.isEmpty() || cur!=null){
                 while (cur!=null){
                     stack.push(cur);
                     cur = cur.left;
                 }
                 cur = stack.pop();
                 //分兩種情況，如果沒有右孩子或右孩子被訪問過了
                 if (cur.right == null || (res.size() != 0 && res.get(res.size() - 1).equals(cur.right.val))){
                     res.add(cur.val);
                     cur = null;
                 }else{
                     stack.push(cur);
                     cur = cur.right;
                 }
             }
             return res;
         }

重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
輸出原始二叉樹

    //前序遍歷
    int[] preorder;
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length  == 0 || in.length == 0)return null;
        this.preorder = pre;
        for(int i = 0;i<in.length;i++){
            map.put(in[i],i);
        }
        return helper1(0,0,in.length -1);
    }
    //pre_root_index:根節(jié)點(diǎn)在前序遍歷中的下標(biāo)位置
    //in_left_index:該節(jié)點(diǎn)在中序遍歷中的左邊界
    //in_right_index:在中序遍歷中的右邊界
    public TreeNode helper1(int pre_root_index,int in_left_index,int in_right_index){
        if (in_left_index > in_right_index) return null;
        //根節(jié)點(diǎn)在中序遍歷中的位置in_root_index
        int in_root_index = map.get(preorder[pre_root_index]);
        //新建節(jié)點(diǎn)
        TreeNode node = new TreeNode(preorder[pre_root_index]);
        //尋找node的左節(jié)點(diǎn)
        //在前序遍歷中的位置就是:根節(jié)點(diǎn)的下標(biāo)+1(右邊一個(gè)單位)
        //在中序遍歷中的位置就是:1.左邊界不變，2.右邊界就是根節(jié)點(diǎn)的左邊一個(gè)單位
        node.left = helper1(pre_root_index+1,in_left_index,in_root_index-1);
        //尋找node的右節(jié)點(diǎn)
        //在前序遍歷中的位置就是:根節(jié)點(diǎn)的下標(biāo)+左子樹的長度+1
        //在中序遍歷中的位置就是:1.左邊界根節(jié)點(diǎn)的右邊一個(gè)單位下標(biāo)+1，2.右邊界不變
        node.right = helper1(pre_root_index + in_root_index - in_left_index + 1,in_root_index+1,in_right_index);
        return node;
    }