频率很高的手写代码面试题--二叉树类型(上)

落日映苍穹つ 2023-07-05 14:29 115阅读 0赞

### 手写代码面试题--二叉树类型上篇 ###

*   *  一、遍历
     *   *  1、二叉树的前序遍历
         *  2、二叉树的中序遍历
         *  3、二叉树的后序遍历
         *  4、二叉树的层次遍历
         *  5、二叉树的锯齿形层次遍历
     *  二、高频
     *   *  6、二叉树的所有路径
         *  7、翻转二叉树
         *  8、重建二叉树
         *  9、二叉树的最大深度
         *  10、二叉树搜索树的第 k 个节点

## 一、遍历 ##

### 1、二叉树的前序遍历 ###

递归写法

def preorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            res = []
            def inorderTree(root):
                if root:
                    res.append(root.val)
                    inorderTree(root.left)
                    inorderTree(root.right)
            inorderTree(root)
            return res

非递归

用非递归写有难度，所以思路要记住，但是我总是忘记，头疼！

**思路**：先定义一个列表，相当于一个栈，初始存放根节点，然后取出栈顶节点，将该节点的值存储在遍历的结果中，将右节点和左节点依次插入到列表中，重复操作，直到列表为空

这里要特别注意左右插入的顺序，我们必须先**插入右子树，然后插入左子树** 虽然python 中的 list 结构插入删除很灵活，但是也必须要满足这个规则。

def preorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            stack = [root]
            output = []
            while stack:
                node = stack.pop()
                if not node:
                    continue
                output.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
            return output

def preorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            stack = [root]
            output = []
            while stack:
            	# 如果没有参数默认是从尾部删除
                node = stack.pop(0)
                if not node:
                    continue
                output.append(node.val)
                # 参数1：在哪个位置插入
                # 参数2：插入的节点
                stack.insert(0,node.right)
                stack.insert(0,node.left)
            return output

### 2、二叉树的中序遍历 ###

递归

def inorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            res = []
            def inorderTraversalTree(root):
                if root:
                    inorderTraversalTree(root.left)
                    res.append(root.val)
                    inorderTraversalTree(root.right)
            inorderTraversalTree(root)
            return res

非递归

def inorderTraversal(self, root: TreeNode) -> List[int]:
            ret, st, n = [], [], root
            while n or st:
                while n:
                    st.append(n)
                    n = n.left
                n = st.pop()
                ret.append(n.val)
                n = n.right
            return ret

### 3、二叉树的后序遍历 ###

递归

def postorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            res = []
            def postorderTree(root):
                if root:
                    postorderTree(root.left)
                    postorderTree(root.right)
                    res.append(root.val)
            postorderTree(root)
            return res

非递归

我们后序遍历的顺序是，左->右->根

如果按照这个顺序写，会非常的困难，但是我们换换思路，我们按照根->右->左的思路遍历，然后进行翻转就可以了！

写法1：

def postorderTraversal(self, root: TreeNode):
            if not root:
                return []
            res,stack = [],[root]
            while stack:
                node = stack.pop()
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            return res[::-1]

写法2：

def postorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            stack = [root]
            res = []
            while stack:
                node = stack.pop()
                if not node:
                    continue
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
            return res[::-1]

### 4、二叉树的层次遍历 ###

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）

> 示例:给定二叉树: \[3,9,20,null,null,15,7\]
> 
>     3
>      / \
>     9  20
>       /  \
>      15   7
>     返回其层次遍历结果：
>     [
>        [3],
>        [9,20],
>        [15,7]
>     ]

**思路**：每一层的节点遍历后放在 level中，并且每个节点用一个列表保存，这个列表相当于队列，每遍历一个节点则弹出一个节点，在弹出去之前，如果他的左右子树存在则插入到末尾。

def levelOrder(self, root: TreeNode):
            if not root:
                return []
            res ,level= [],[root]
            while level:
                temp = []
                n = len(level)
                for _ in range(n):
                    node = level.pop(0)
                    if node.left:
                        level.append(node.left)
                    if node.right:
                        level.append(node.right)
                    temp.append(node.val)
                res.append(temp)
            return res

方法二：

其实 for 循环的用法在python中是非常灵活的，首先看看下面这段代码

res = []
    temp = []
    for i in range(10):
        temp.append(i)
    res.append(temp)
    print(res) # [[1,2,3,4,5,6,7,8,9]]

上面六七行代码可以用下面这行代替

res = []
    res.append([i for i in range(10)])
    print(res) # [[1,2,3,4,5,6,7,8,9]]

再看下面这段

res = [(i*1, i*2)for i in range(10)]
    print(res)
    
    temp = []
    for i in res:
        for j in i:
            temp.append([j])
    print(temp)

红色框第一行的初始化，粉色框是遍历出元素，因为res 是一个二维的列表结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]

def levelOrder(root):
        if not root:
            return []
        res,level = [],[root]
        while level:
            res.append([node.val for node in level])
            temp = [[node.left,node.right]for node in level]
            level = [j for i in temp for j in i if j]
        return res

方法三：深度优先搜索

先左子树后右子树，搜索的时候保存搜索的深度值，深度值相同的节点放在一起

def levelOrder(self, root):
            res = []
            def dfs(root, level):
                if root:
                    if len(res)<level+1:
                        res.append([])
                    res[level].append(root.val)
                    dfs(root.left, level+1)
                    dfs(root.right, level+1)
            dfs(root, 0)
            return res

进阶：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

> 示例  
> 给定二叉树 \[3,9,20,null,null,15,7\]
> 
>     3
>      / \
>     9  20
>       /  \
>      15   7
>      返回其自底向上的层次遍历为：
>     [
>       [15,7],
>       [9,20],
>       [3]
>     ]

思路和之前是一样的，只不过之前是进行尾插append函数，这次要进行头插的操作。

def levelOrderBottom(root):
    	if not root:
        	return []
        res,level = [],[root]
        while level:
        	res = [[node.val for node in level]] +res
            temp =[[node.left,node.right] for node in level]
            level = [j for i in temp for j in i if j]
    	return res

### 5、二叉树的锯齿形层次遍历 ###

给定一个二叉树，返回其节点值的锯齿形层次遍历

即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行

1
       /   \
      2     3
     / \   / \
    4  5  6   7

首先打印1，然后打印 3，2，然后打印4,5，6,7  
规则就是，奇数行从左往右，偶数行从右往左

方法一：利用两个栈进行交换保存，虽然代码看起来挺多，但还是比较好理解的

vector<vector<int> > Print(TreeNode* pRoot) { 
            vector<vector<int>>res;
            if(pRoot == nullptr){ 
                return res;
            }
            // 定义两个栈，分别保存奇数行和偶数行
            stack<TreeNode*>s1;
            stack<TreeNode*>s2;
            vector<int>temp;// 临时数组
            temp.push_back(pRoot->val);
            res.push_back(temp);
            s1.push(pRoot);
            temp.clear();
            while(!s1.empty() || !s2.empty()){ 
                while(!s1.empty()){ 
      				// 遍历 s1 栈，每遍历一个弹出一个
                    TreeNode* node = s1.top();
                    s1.pop();
                    if(node->right){ 
                        s2.push(node->right);
                        temp.push_back(node->right->val);
                    }
                    if(node->left){ 
                        s2.push(node->left);
                        temp.push_back(node->left->val);
                    }
                }
                // 最后插入完后，要情况一下
                if(!temp.empty()){ 
                    res.push_back(temp);
                    temp.clear();
                }
                while(!s2.empty()){ 
                	// 遍历 s2 栈，每遍历一个弹出一个
                    TreeNode* cur = s2.top();
                    s2.pop();
                    if(cur->left){ 
                        s1.push(cur->left);
                        temp.push_back(cur->left->val);
                    }
                    if(cur->right){ 
                        s1.push(cur->right);
                        temp.push_back(cur->right->val);
                    }
                }
    			// 最后插入完后，要情况一下
                if(!temp.empty()){ 
                    res.push_back(temp);
                    temp.clear();
                }
            }
            return res;
        }

方法二：

class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            vector<vector<int>>res;
            if(root == nullptr){ 
                return res;
            }
            queue<TreeNode*>q;
            q.push(root);
            bool isLeft = false;
            while(!q.empty()){ 
                int size = q.size();
                vector<int>temp;
                for(int i = 0;i<size;++i){ 
                    TreeNode* node = q.front();
                    q.pop();
                    temp.push_back(node->val);
                    if(node->left){ 
                        q.push(node->left);
                    }
                    if(node->right){ 
                        q.push(node->right);
                    }
                }
                isLeft = !isLeft;
                if(!isLeft){ 
                    res.push_back(vector<int>(temp.rbegin(),temp.rend()));
                }else{ 
                    res.push_back(temp);
                }
            }
            return res;
        }
    };

## 二、高频 ##

### 6、二叉树的所有路径 ###

给定一个二叉树，返回所有从根节点到叶子节点的路径

说明: 叶子节点是指没有子节点的节点

示例,输入:
    
        1
       / \
      2   3
       \
        5
    输出: ["1->2->5", "1->3"]

方法一：递归

先往左子树搜，再往右子树搜，记录访问过的节点  
停止的条件是到了叶子节点，即该节点没有孩子节点了，这时候进行插入，然后把它用 `->` 分割开来

def binaryTreePaths(self, root: TreeNode) -> List[str]:
            res = []
            if not root:
                return res
            def dfs(root,path):
                if not root.left and not root.right:
                    res.append('->'.join(path+[str(root.val)]))
                if root.left:
                    dfs(root.left,path+[str(root.val)])
                if root.right:
                    dfs(root.right,path+[str(root.val)])
            dfs(root,[])
            return res

C++ 版本:思路基本一致

void dfs(TreeNode* root,string str,vector<string>&res){ 
            if(root->left == NULL && root->right==NULL){ 
                str += to_string(root->val);
                res.push_back(str);
                return;
            }
            str +=to_string(root->val) + "->";
            if (root->left){ 
                dfs(root->left,str,res);
            }
            if (root->right){ 
                dfs(root->right,str,res);
            }
        }
        vector<string> binaryTreePaths(TreeNode* root) { 
            vector<string>res;
            if(root == NULL){ 
                return res;
            }
            string str = "";
            dfs(root,str,res);
            return res;
        }

方法二：非递归，利用栈

vector<string> binaryTreePaths(TreeNode* root) { 
            vector<string> ans;
            if(root==NULL) { 
            	return ans;
            }
            TreeNode* p=root;
            stack<pair<TreeNode*,string>> s;
            string str;
            while(!s.empty() || p){ 
                while(p){ 
                    if(p==root){ 
                    	str=str+to_string(p->val);
    				}else{ 
                    	str=str+"->"+to_string(p->val);
                    }
                    s.push(pair<TreeNode*,string>(p,str));
                    p=p->left;
                }
                p=s.top().first;
                str=s.top().second;
                s.pop();
                if(p->right==NULL&&p->left==NULL) 
                	ans.push_back(str);
                p=p->right;
            }
            return ans;
        }

非递归，利用队列

vector<string> binaryTreePaths(TreeNode* root) { 
            vector<string>res;
            if(root == nullptr){ 
                return res;
            }
            queue<pair<TreeNode*,string>>q;
            q.push(pair<TreeNode*,string>\
    	        (root,to_string(root->val)));
    	        
            while(!q.empty()){ 
                TreeNode* node =  q.front().first;
                string path = q.front().second;
                q.pop();
                if(node->left == nullptr &&
                   node->right == nullptr){ 
                    res.push_back(path);
                }
                if(node->left){ 
                    q.push(pair<TreeNode*,string>\
                    	(node->left,path + "->"+to_string\
    	                (node->left->val)));
                }
                if(node->right){ 
                    q.push(pair<TreeNode*,string>\
       		        	(node->right,path + "->"+to_string\
                    	(node->right->val)));
                }
            }
            return res;
        }

### 7、翻转二叉树 ###

翻转一棵二叉树

方法一：递归

def invertTree(self, root: TreeNode) -> TreeNode:
    	if root:
        	root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
    	return root

C++ 版本

TreeNode* invertTree(TreeNode root) { 
    	if (root == null) { 
        	return null;
    	}
        TreeNode* temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        return root;
    }

方法二 ：非递归，利用一个队列进行迭代

TreeNode* invertTree(TreeNode* root) { 
            if(root==nullptr){ 
                return nullptr;
            }
            queue<TreeNode*>que;
            que.push(root);
            while(!que.empty()){ 
                TreeNode* cur = que.front();
                que.pop();
                TreeNode* temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
                if(cur->left){ 
                    que.push(cur->left);
                }
                if(cur->right){ 
                    que.push(cur->right);
                }
            }
            return root;
        }

### 8、重建二叉树 ###

根据前序数列和中序数列构建二叉树

> 前序遍历 preorder = \[3,9,20,15,7\]  
> 中序遍历 inorder = \[9,3,15,20,7\]

输出

3 
       /   \ 
      9    20
          /  \
        15    7

思路：前序遍历的第一个节点是 root 根节点，根据这个根节点在中序遍历中分成左子树和右子树，然后递归实现构建二叉树

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
            int end = preorder.size()-1;
            return build(preorder,inorder,0,0,end);
        }
        TreeNode* build(vector<int>& preorder, vector<int>& inorder,\
        			int root,int start,int end)
        { 
            if(start>end){ 
                return nullptr;
            }
            TreeNode* tree = new TreeNode(preorder[root]);
            int i = start;
            while(i<end && preorder[root] != inorder[i]){ 
                ++i;
            }
            tree->left = build(preorder,inorder,root+1,start,i-1);
            tree->right = build(preorder,inorder,root+1+i-start,i+1,end);
            return tree;
        }

可以对中序列表设置一个 unordered\_map 容器，方便遍历

unordered_map<int, int> mp;
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
            for (int i = 0; i < inorder.size(); i++) { 
                mp[inorder[i]] = i;
            }
            return dfs(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
        }
        
        TreeNode* dfs(const vector<int>& preorder, int pl, int pr, const vector<int>& inorder, int il, int ir) { 
            if (pl > pr) return NULL;
            TreeNode *root = new TreeNode(preorder[pl]);
            int idx = mp[root->val];
            int cntL = idx - il;
            root->left = dfs(preorder, pl + 1, pl + cntL, inorder, il, idx-1);
            root->right = dfs(preorder, pl + cntL + 1, pr, inorder, idx+1, ir);
            return root;
        }

如果上面代码不好理解，那这个应该比较简单点

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 
            if(vin.size()==0){ 
                return 0;
            }
            // 定义四个数组
            vector<int>pre_left,pre_right,vin_left,vin_right;
            // 只有下面这一行代码是核心，其余都是准备工作
            TreeNode* root = new TreeNode(pre[0]);
            int temp = 0;
            for(int i = 0;i < vin.size();++i){ 
                if(vin[i] == pre[0]){ 
                    temp = i;
                    break;
                }
            }
            for(int i = 0;i < temp;++i){ 
                pre_left.push_back(pre[i+1]);
                vin_left.push_back(vin[i]);
            }
            for(int i = temp+1;i < vin.size();++i){ 
                pre_right.push_back(pre[i]);
                vin_right.push_back(vin[i]);
            }
            root->left = reConstructBinaryTree(pre_left,vin_left);
            root->right = reConstructBinaryTree(pre_right,vin_right);
            return root;
        }

### 9、二叉树的最大深度 ###

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

**思路**： 递归这个其实没啥思路，就是先遍历左子树，然后遍历右子树，通过比较左右子树那个更深，返回更深的那个数+1

def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            left = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            return max(left,right)+1

但是试试可不可以用循环实现

把每一层的节点保存为一个列表，然后每一层完之后进行计数+1

def maxDepth(self, root: TreeNode) -> int:
            if not root:
                return 0
            temp = [root]
            level = 0
            while temp:
                n = len(temp)
                # 这里使用的是列表，其实它相当于一个队列
                for _ in range(n):
                    node = temp[0]
                    if node.left:
                        temp.append(node.left)
                    if node.right:
                        temp.append(node.right)
                    temp.pop(0)
                level+=1
            return level

python 比c++好写多了，列表使用特别灵活，既可以当栈，也可以当队列，不需要去记c++中 头插，头删等库函数

### 10、二叉树搜索树的第 k 个节点 ###

TreeNode* res = nullptr;
        int count = 0;
        TreeNode* KthNode(TreeNode* pRoot, int k){ 
            if(pRoot == nullptr || k < 1){ 
                return nullptr;
            }
            count = k;
            KthNodeIn(pRoot);
            return res;
        }
        void KthNodeIn(TreeNode* pRoot){ 
            if(pRoot == nullptr){ 
                return;
            }
            KthNodeIn(pRoot->left);
            if(--count ==0){ 
                res = pRoot;
            }
            KthNodeIn(pRoot->right);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191128223109262.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70