【左神】二叉树基础复习

超、凢脫俗 2022-09-08 03:56 128阅读 0赞

## 二叉树的经典遍历 ##

### 【前序遍历】 ###

迭代法需要stack来保存临时节点，先右后左，因为是stack

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

时刻注意stack的入栈顺序和出栈顺序是不一样的

class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<Integer>();
            if(root!=null) {
        
                Stack<TreeNode> stack = new Stack<TreeNode>();
                stack.push(root);
                //stack里面是先右后左
                while(!stack.isEmpty()) {
        
                    root = stack.pop();
                    list.add(root.val);
                    if(root.right!=null) stack.push(root.right);
                    if(root.left!=null) stack.push(root.left);
                }
            }
            return list;
        }
    }

### 【后序遍历】 ###

后续遍历需要两个stack，因为需要倒一下，倒出来，和前序遍历是相反的；前面是弹出就收集，这里是弹出的时候先放到一个地方，等stack2装完了再倒出来。

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

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

### 【中序遍历】 ###

只要有左就不断遍历左边，一直放到栈中，遇到左边变为空之后，开始弹出栈里面的东西，弹出的时候开始收集信息，往右转移一个位置，又开始不断的向左边遍历。

1、迭代法：

> 中序遍历：一直遍历左边

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

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

根先出来前序遍历，根不断向左走中序遍历，俩stack配合是后序遍历

### 【层序遍历】 ###

public void cengxuOrder(TreeNode head) {
        
    	if(head == null) return;
    	List<Integer> list = new ArrayList<>();
    	Queue queue = new LinkedList<Integer>();
    	queue.add(head);
    	while( !queue.isEmpty() ) {
        
    		TreeNode cur = queue.poll();
    		list.add(cur.val);
    		if(cur.left!=null) queue.add(cur.left);
    		if(cur.right!=null) queue.add(cur.right);
    	}
    }

### 【二叉树的深度优先遍历】 ###

求一颗二叉树的宽度

先放左后放右，弹出就打印

### 层序遍历 ###

**层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。**

广度优先搜索——层序遍历就是逐层遍历树结构。

队列的先进先出思想使得站在出口的总是头节点。而且总是偏左边的

class Solution {
        
        public void levelOrder(TreeNode root) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            if (root == null) return;
            queue.add(root);
            while (!queue.isEmpty()) {
        
                TreeNode cur = queue.poll();
                // Sys.out !
                if (cur.left!=null) queue.add(cur.left);
                if (cur.right!=null) queue.add(cur.right);
            }
        }
    }

有特定的输出需求的：

class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> bigList = new ArrayList<>();
            if (root == null) return bigList;
    
            queue.add(root);
            while (!queue.isEmpty()) {
        
                List<Integer> list = new ArrayList<>();
                int size = queue.size();
                //一次循环将一个父节点加入到list中，最后遍历完成后，一层的list完成装载
                for (int i = 0; i < size; i++) {
        
                    TreeNode cur = queue.poll();
                    list.add(cur.val);
                    if (cur.left!=null) queue.add(cur.left);
                    if (cur.right!=null) queue.add(cur.right);
                }
                bigList.add(list);
            }
            return bigList;
        }
    }

## 递归思想 ##

【1】

尝试使用 “`自顶向下`” 的递归来解决此问题。

1.  你能确定一些参数，从该节点自身解决出发寻找答案吗？
2.  你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？

【2】

对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 如果答案是肯定的，那么 “`自底向上`” 的递归可能是一个不错的解决方法。

https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefb4e/

运用递归解决树的问题

## 套路：树型DP ##

### 是否平衡二叉树 ###

class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            return process(root).isBalance;
        }
    
        public static Info process(TreeNode cur) {
        
            if (cur == null) {
        
                return new Info(true, 0);
            }
            Info lData = process(cur.left);
            Info rData = process(cur.right);
    
            boolean isBalance = false;
            //如果是左右子树都是二叉树并且他们的高度都满足要求，那么就等于true；
            if((lData.isBalance && rData.isBalance 
                    && Math.abs(lData.height - rData.height)<=1)){
        
                isBalance = true;
            }
            int height = Math.max(lData.height, rData.height)+1;
            return new Info(isBalance, height);
        }
    
        public static class Info{
        
            boolean isBalance;
            int height;
    
            Info(boolean isBT, int height){
        
                this.isBalance = isBT;
                this.height = height;
            }
        }
    }

### 是否对称 ###

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root == null)
                return true;
            return dfs(root.left, root.right);
        }
    
        public boolean dfs(TreeNode left, TreeNode right) {
        
            if(left == null && right == null)
                return true;
            if(left == null || right == null || left.val != right.val)
                return false;
            return dfs(left.left, right.right) && dfs(left.right, right.left);
        }
    }

## 树型DP问题 ##

### 最低公共祖先 ###

注意p,q必然存在树内, 且所有节点的值唯一!!!

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            HashMap<TreeNode, TreeNode> fatherMap = new HashMap<>();
            setFather(fatherMap, root);
            Set<TreeNode> set = new HashSet<>();
    
            TreeNode cur = p;
            while(cur != root) {
        
                set.add(cur);
                cur = fatherMap.get(cur);
            }
            fatherMap.put(root, root);
            
            cur = q;
            while(cur != root) {
        
                if(set.contains(cur)) return cur;
                cur = fatherMap.get(cur);
            }
            return root;
        }
        public static void setFather(HashMap fatherMap, TreeNode node) {
        
            if(node == null) return;
            fatherMap.put(node.left, node);
            fatherMap.put(node.right, node);
            setFather(fatherMap, node.left);
            setFather(fatherMap, node.right);
        }
    }

### 后继节点 ###

[510. 二叉搜索树中的中序后继 II][510. _ II]

1）有右树的时候，那么就是右树的最左节点

2）没有右树的时候，向上找，判断自己是不是父亲的左孩子

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;
    };
    */
    
    class Solution {
        
        public Node inorderSuccessor(Node node) {
        
            if (node == null) return node;
            if (node.right != null) {
        
                return getLeft(node.right);
            } else {
        
                Node parent = node.parent;
                while (parent!=null && parent.right == node){
        
                    node = parent;
                    parent = node.parent;
                }
                return parent;
            }
        }
    
        public static Node getLeft(Node node) {
        
            if (node == null) return node;
            while(node!=null && node.left!=null) {
        
                node = node.left;
            }
            return node;
        }
    }

### 序列化 ###

层序遍历

class Solution {
        
        public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            //checkFun01(root,0);
            checkFun02(root);
    
            return resList;
        }
    
        //DFS--递归方式
        public void checkFun01(TreeNode node, Integer deep) {
        
            if (node == null) return;
            deep++;
    
            if (resList.size() < deep) {
        
                //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
                List<Integer> item = new ArrayList<Integer>();
                resList.add(item);
            }
            resList.get(deep - 1).add(node.val);
    
            checkFun01(node.left, deep);
            checkFun01(node.right, deep);
        }
    
        //BFS--迭代方式--借助队列
        public void checkFun02(TreeNode node) {
        
            if (node == null) return;
            Queue<TreeNode> que = new LinkedList<TreeNode>();
            que.offer(node);
    
            while (!que.isEmpty()) {
        
                List<Integer> itemList = new ArrayList<Integer>();
                int len = que.size();
    
                while (len > 0) {
        
                    TreeNode tmpNode = que.poll();
                    itemList.add(tmpNode.val);
    
                    if (tmpNode.left != null) que.offer(tmpNode.left);
                    if (tmpNode.right != null) que.offer(tmpNode.right);
                    len--;
                }
    
                resList.add(itemList);
            }
    
        }
    }

### 填充每个节点的下一个右侧节点指针 ###

本题依然是层序遍历（每一层是反着的队列），只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {
        
        public Node connect(Node root) {
        
            if(root == null) return root;
            Queue<Node> que = new LinkedList<>();
            que.offer(root);
            
            // 把队列反着排序，那么我们就可以保存每一行的最后一个结点，
            // 然后让前面的指针指向我们保存好的后面的结点就ok。
            while(!que.isEmpty()) {
        
                int len = que.size();
                Node nextNode = null;
                while(len-- > 0) {
        
                    Node cur = que.poll();
                    cur.next = nextNode;
                    nextNode = cur;
                    if (cur.right!=null) que.offer(cur.right);
                    if (cur.left!=null) que.offer(cur.left);
                }
            }
            return root;
        }
    }

[510. _ II]: https://leetcode-cn.com/problems/inorder-successor-in-bst-ii/