树(刷题更新)

朱雀 2022-05-12 11:26 135阅读 0赞

## 树常用操作: ##

## 一.遍历 ##

遍历主要分为按层遍历(广度优先遍历)、深度优先遍历。

**1.按层遍历：**

核心代码：

//队列
    	Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    	//记录当前的结点
    	TreeNode cur;
    	//入队
    	queue.offer(root);
    	while(!queue.isEmpty()){ 
    		//出队
    		cur = queue.poll()
    	    
    	    if(cur.left!=null){ 
    			   queue.offer(cur.left);
    		}
    	    
    	    if(cur.right!=null){ 
    			   queue.offer(cur.right);
    		}
    	}

**2.深度优先遍历:**

又分为递归和非递归。  
递归:  
核心代码:

public void depthTraversal(TreeNode root)  
        {   
            if (root!=null)   
            {   
                depthTraversal(root.left);  
                depthTraversal(root.right);  
            }         
        }

非递归：  
核心代码

Stack<TreeNode> stack=new Stack<TreeNode>();
            stack.push(root);
            while(!stack.isEmpty()){ 
                TreeNode tree=stack.pop();
                if(tree.right!=null)
                    stack.push(tree.right);
                if(tree.left!=null)
                    stack.push(tree.left);
            }

**3.中序遍历**  
树的中序遍历的非递归

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

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关《二叉树刷题计划》——平衡二叉树

二叉树相关OJ题目——二叉树的高度，平衡二叉树的判断

太过爱你忘了你带给我的痛/ 2024年04月23日 15:39/ 0 赞/ 83 阅读

相关树——算法专项刷题（八）

八、树主要是对二叉树的前、中、后、层序遍历的应用（这四种遍历详见 [二叉树遍历][Link 1]） 8.1二叉树的最近公共祖先 [原题链接][Link 2

本是古典何须时尚/ 2024年03月31日 01:18/ 0 赞/ 87 阅读

相关 leecode刷题经验(java/C)持续更新

双指针例题1 给你一个非严格递增排列的数组 `nums` ，请你\\[ 原地][Link 1]\\ 删除重复出现的元素，使每个元素只出现一次，返回删除后数

- 日理万妓/ 2024年02月22日 04:33/ 0 赞/ 49 阅读

相关二叉树面试题刷题模板[终极版]

文章目录递归树结构二叉树的最大深度后序递归二叉树最小深度后序递归

心已赠人/ 2022年12月22日 08:59/ 0 赞/ 150 阅读

相关力扣刷题：二叉树篇

目录 100. 相同的树题目介绍题目实现 101. 对称二叉树题目介绍 \[剑指 Off

电玩女神/ 2022年10月16日 09:40/ 0 赞/ 235 阅读

相关刷题必备基础知识：二叉树

目录 1. 前言 2. 二叉树的遍历 2.1 递归法 2.1.1 前序遍历 2.1.2 中序遍历

雨点打透心脏的1/2处/ 2022年09月09日 01:56/ 0 赞/ 138 阅读

相关位操作(刷题更新 )

位运算 &:按位与运算，两个都为1时，才为1。 |:按位或运算，两个都为0时，才为0。 ^:异或运算，两个位相同位0，相异为1。 ~:取反

╰半夏微凉°/ 2022年05月13日 12:36/ 0 赞/ 161 阅读

相关树(刷题更新)

树常用操作: 一.遍历遍历主要分为按层遍历(广度优先遍历)、深度优先遍历。 1.按层遍历：核心代码： //队列 Queue<TreeNo

朱雀/ 2022年05月12日 11:26/ 0 赞/ 136 阅读

相关数组(刷题更新)

数组的常见题型 1.次数超过数组长度一半的那个数字(或者众数) 核心代码: public int findMoreThanHalfNum(int[] number

曾经终败给现在/ 2022年05月11日 04:00/ 0 赞/ 136 阅读

相关树——牛客网刷题第二波

发现牛客网很不稳定，刷的是“树”，时不时冒出几个“图”，emmm，对于强迫症的我真是煎熬，还在想要不要把标题改喽——树图~~~~暂时先这样吧~~~~ 1.一棵左右子树均不空

客官°小女子只卖身不卖艺/ 2022年01月26日 01:31/ 0 赞/ 300 阅读