Day24---二叉树专题

---

二.迭代实现

1.前序遍历

**思路：**用栈模拟前序遍历过程，由于是栈（先进后出）

• 根节点先栈
• 当栈不为空，右孩子先入栈，然后左孩子再入栈（后进先出）

**栈模拟：**根左右 —> 根右左

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.中序遍历

思路：

1. 处理：将元素放进result数组中
2. 访问：遍历节点

中：左根右

迭代法：

• 定义一个指针指向根节点，当节点不为空或者栈不为空时一直循环
• 当指针不为空时，当前节点入栈，一直循环遍历左儿子，如此往复直到p指针指向空-------（模拟一直左递归的过程）
• 当指针为空时，栈顶元素出栈，指针指向了出栈的节点,p = stk.pop()，节点值val加入result（模拟遍历中根的过程，记录答案），然后指针p移动到当前节点的右儿子（模拟遍历中右的过程），为下一次（左根右做好准备）

遍历左儿子为空时，弹出栈中元素。遍历右儿子为空时，继续弹出栈中元素。

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.后序遍历

思路：

看后序遍历，前序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中。

• 根左右 —> 由入栈顺序根右左得到
• 那么根右左 —> 由入栈顺序根左得到

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4.层序遍历二叉树

**思路：**队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。对头先入队，当队列不为空时，（遍历此时队列中的所有元素）对头元素逐一出队（队头出），加入答案（每一层），的元素，然后将该元素的左右儿子入队（队尾入），当前层遍历完后，将这层的答案记录，进入下一层。直到最后队列为空。每次遍历层的时候，需要记录队列的大小，以便需要弹出多少元素。

代码实现:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itList = new ArrayList<Integer>();
            int len = queue.size();
            while(len>0){
                TreeNode tmpNode = queue.poll();
                itList.add(tmpNode.val);
                if(tmpNode.left!=null) queue.add(tmpNode.left);
                if(tmpNode.right!=null) queue.add(tmpNode.right);
                len--;
            }
            result.add(itList);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.翻转二叉树

递归三部曲：

1.确定递归函数的参数和返回值：返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数

2.确定终止条件：当前节点为空的时候，就返回

3.确定单层递归的逻辑：因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树

思路：递归实现

• 如果根节点不为空，那么就要交换其左右子树（即使左右子树是空节点也没关系）
• 递归交换左右子树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        dfs(root);
        return root;
    }
    public static void dfs(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        dfs(root.left);
        dfs(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路二:BFS

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24