資料結構每日學習 Day1 二元樹

第一題：

114. 二元樹展開為連結串列

解題：
首先回顧一下 二元樹的遞迴遍歷和迭代遍歷

遞迴遍歷如下：
(三種遍歷方式只需調整add語句位置即可)

    public void dfs(TreeNode root,List<TreeNode> list){
        if (root!=null){
            list.add(root);
            dfs(root.left,list);
            dfs(root.right,list);
        }

    }

迭代遍歷+Morris解法如下：

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
中序迭代（自認為好理解的）：

public static void inOrderIteration(TreeNode head) {
	if (head == null) {
		return;
	}
	TreeNode cur = head;
	Stack<TreeNode> stack = new Stack<>();
	while (!stack.isEmpty() || cur != null) {
		while (cur != null) {
			stack.push(cur);
			cur = cur.left;
		}
		TreeNode node = stack.pop();
		System.out.print(node.value + " ");
		if (node.right != null) {
			cur = node.right;
		}
	}
}

前序迭代：（這個畫個圖 理解一下就很快）

public static void preOrderIteration(TreeNode head) {
	if (head == null) {
		return;
	}
	Stack<TreeNode> stack = new Stack<>();
	stack.push(head);
	while (!stack.isEmpty()) {
		TreeNode node = stack.pop();
		System.out.print(node.value + " ");
		if (node.right != null) {
			stack.push(node.right);
		}
		if (node.left != null) {
			stack.push(node.left);
		}
	}
}

感覺下面這個更好理解一些

Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                list.add(node);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }

AC：

package 二元樹;

import java.util.ArrayList;
import java.util.List;

public class 二元樹展開為連結串列 {
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }

  /*
  Queue<TreeNode> queue = new ArrayDeque<>();
        preOrder(root, queue);
        while (!queue.isEmpty()){
            TreeNode curr = queue.poll();
            curr.left = null;
            curr.right = queue.peek();
        }
    }
   */
    public void flatten(TreeNode root) {
        List<TreeNode> list=new ArrayList<TreeNode>();
        dfs(root,list);
        int len=list.size();
        
        for (int i = 1; i <len ; i++) {
            //原本下面這一行錯了 注意理解
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left=null;
            prev.right=curr;

        }



    }
    public void dfs(TreeNode root,List<TreeNode> list){
        if (root!=null){
            list.add(root);
            dfs(root.left,list);
            dfs(root.right,list);
        }

    }
}

第二題：543. 二元樹的直徑

AC:(太妙了 首先你要會深度是怎麼求的 ！！！ )（這個遞迴過程建議反覆咀嚼）

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 存取到空節點了，返回0
        }
        int L = depth(node.left); // 左兒子為根的子樹的深度
        int R = depth(node.right); // 右兒子為根的子樹的深度
        ans = Math.max(ans, L+R+1); // 計算d_node即L+R+1 並更新ans
        return Math.max(L, R) + 1; // 返回該節點為根的子樹的深度
    }
}