Day24——二叉树专题

港控/mmm° 2024-04-01 13:26 74阅读 0赞

#### 文章目录 ####

*   *   *  二.迭代实现
         *   *  1.前序遍历
             *  2.中序遍历
             *  3.后序遍历
             *  4.层序遍历二叉树
             *  5.翻转二叉树

--------------------

#### 二.迭代实现 ####

##### 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;
        }
    }

##### 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;
        }
    }

##### 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;
        }
    }

##### 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;
        }
    }

##### 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);
        }
    }

思路二: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;
        }
    }