六、樹

6.1遍歷算法

6.1.1前中后序

• 在做遞歸時，最重要是三步驟

  1. 確定遞歸函數(shù)的返回值和參數(shù)

  2. 確定終止條件

  3. 確定單層遞歸的邏輯

     偽代碼
     void travel(cur, vec) {if (cur == null) {return ;}vec.push(cur->middle, vec);  // 遞歸中節(jié)點vec.push(cur->left, vec);    // 遞歸左節(jié)點vec.push(cur->right, vec);   // 遞歸右節(jié)點
     }
     

  • 其實很簡單，參數(shù)就是要目前遍歷節(jié)點在哪，返回值也同理，終止條件就是指遍歷到null的時候回溯，邏輯不要想復(fù)雜，根據(jù)順序移動上述上個遞歸函數(shù)即可

  • 前順遍歷

    class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return; }result.add(root.val);  // 中節(jié)點preorder(root.left, result);   // 左子樹preorder(root.right, result);  // 右子樹}
    }
    

  • 中序遍歷

    class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}public void inorder(TreeNode root, List<Integer> res) {if (root == null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
    }
    

  • 后序遍歷

    class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result);   postorder(root.right, result);result.add(root.val);}
    }
    

  • 其實很簡單，根據(jù)遍歷的順序擺放遍歷順序和添加元素的順序，(root.left, result)代表左子樹，(root.right, result)代表右子樹，(root.val)代表中節(jié)點。

  • 遞歸

  • 前序（要理解遍歷的核心，先把中節(jié)點塞入，然后根據(jù)棧去模擬，先加入右節(jié)點然后是左節(jié)點，移動到左節(jié)點繼續(xù)加入）

    class Solution {public List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.right != null) {stack.push(temp.right);}if (temp.left != null) {stack.push(temp.left);}}return res;}
    }
    

  • 中序（核心就是每收集一個元素到res數(shù)組中，其實都是以中節(jié)點的姿態(tài)進入，這也對應(yīng)了為什么if循環(huán)為什么要push一個null節(jié)點，前中后也只要交換順序即可）

    class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root != null) stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.peek();if (temp != null) {stack.pop();if (temp.right != null) stack.add(temp.right);stack.push(temp);stack.push(null);if (temp.left != null) stack.add(temp.left);}else {stack.pop();temp = stack.peek();stack.pop();res.add(temp.val);}}return res;}
    }
    

  • 后序（就是前序遍歷的左右調(diào)換順序，然后再倒敘結(jié)果數(shù)組）

    class Solution {public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();if (root == null){return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode temp = stack.pop();res.add(temp.val);if (temp.left != null) {stack.push(temp.left);}if (temp.right != null) {stack.push(temp.right);}}Collections.reverse(res);return res;}
    }
    

6.1.2層序遍歷

1. 遞歸算法，一般遞歸就是深度優(yōu)先了，要明確三要素，一般遍歷就是參數(shù)為當(dāng)前處理節(jié)點+加其它附屬條件，循環(huán)處理按照順序（這里是左到右），結(jié)束條件都是到底直接返回

   class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {check(root, 0);return res;}public void check(TreeNode temp, int deep) {if (temp == null) {return;}deep++;if (res.size() < deep) {  // 創(chuàng)建數(shù)組的條件，不可能預(yù)先創(chuàng)建的List<Integer> res1 = new ArrayList<>();res.add(res1);}res.get(deep-1).add(temp.val);  // 注意為deep-1，區(qū)分索引和深度的區(qū)別check(temp.left, deep);  // 左子樹check(temp.right, deep);  // 右子樹}
   }
   

2. 迭代，就是按照隊列，先進先出，按照層數(shù)模擬也就是廣度優(yōu)先遍歷

   class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> queue = new ArrayDeque<>();List<List<Integer>> res = new ArrayList<List<Integer>>();  // 結(jié)果二維數(shù)組if (root != null) {queue.addLast(root);  // 防止root為空}while (!queue.isEmpty()) {int size = queue.size();  // size代表每一層幾個元素List<Integer> res1 = new ArrayList<>();while (size > 0) {  // size為0這一層就停止TreeNode temp =  queue.removeFirst();res1.add(temp.val);if (temp.left != null) queue.addLast(temp.left);  // 左節(jié)點if (temp.right != null) queue.addLast(temp.right);  // 右節(jié)點size--;  // 記得減一}res.add(res1);}return res;}
   }