摘要:題目給定一個二叉樹,返回其節點值的鋸齒形層次遍歷。例如給定二叉樹返回鋸齒形層次遍歷如下題解這道題要求用字型就是要求知道深度。稍作改動的是需要在遍歷左子樹和右子樹的時候帶上深度的信息,才能知道是加在列表頭還是列表尾部。
題目
給定一個二叉樹,返回其節點值的鋸齒形層次遍歷。(即先從左往右,再從右往左進行下一層遍歷,以此類推,層與層之間交替進行)。
例如:
給定二叉樹 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回鋸齒形層次遍歷如下:
[ [3], [20,9], [15,7] ]題解
這道題要求用z字型,就是要求知道深度。因為知道深度我們就可以根據深度的奇偶來判斷如何打印。
首先相到的就是層序遍歷,然后記錄是第幾層。層序遍歷用隊列的代碼我們已經很熟悉了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List> zigzagLevelOrder(TreeNode root) { List
> res = new LinkedList<>(); if (root == null) { return res; } LinkedList
queue = new LinkedList<>(); queue.add(root); int depth = 0; while (!queue.isEmpty()) { int size = queue.size(); LinkedList currentRes = new LinkedList<>(); // 當前層一直出隊. while (size > 0) { TreeNode current = queue.poll(); TreeNode left = current.left; TreeNode right = current.right; if (left != null) { queue.add(left); } if (right != null) { queue.add(right); } // 奇數層,從頭添加; 偶數層從尾部添加. if (depth % 2 != 0) { currentRes.add(0, current.val); } else { currentRes.add(current.val); } size--; } // 把當前層遍歷的結果加入到結果中. res.add(currentRes); depth++; } return res; } }
同之前一樣,我們想一想有沒有遞歸的解法.
我們可以采用先序遍歷的方式,先遍歷節點,然后遞歸的遍歷左子樹和右子樹。
稍作改動的是,需要在遍歷左子樹和右子樹的時候帶上深度的信息,才能知道是加在列表頭還是列表尾部。
遞歸的結束條件就是遇到空節點。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List熱門閱讀> zigzagLevelOrder(TreeNode root) { List
> res = new LinkedList<>(); if (root == null) { return res; } helper(res, root, 0); return res; } public void helper(List
> res,TreeNode root, int depth) { if (root == null) { return; } // 注意這里new List, 說明當前節點遞歸進入了新的層. if (res.size() <= depth) { res.add(new LinkedList<>()); } if (depth % 2 != 0) { res.get(depth).add(0, root.val); } else { res.get(depth).add(root.val); } helper(res, root.left, depth + 1); helper(res, root.right, depth + 1); } }
技術文章匯總
【Leetcode】101. 對稱二叉樹
【Leetcode】100. 相同的樹
【Leetcode】98. 驗證二叉搜索樹
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73450.html
摘要:題目地址題目描述給定一個二叉樹,返回其節點值的鋸齒形層次遍歷。即先從左往右,再從右往左進行下一層遍歷,以此類推,層與層之間交替進行。解答二叉樹的層序遍歷,只不過對于偶數層來說,把該層的遍歷結果轉置一下就行了。 題目地址:https://leetcode-cn.com/probl...題目描述:給定一個二叉樹,返回其節點值的鋸齒形層次遍歷。(即先從左往右,再從右往左進行下一層遍歷,以此類...
摘要:有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像,都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸,所以空間復雜度為 ...
摘要:題目給定一個二叉樹,返回其按層次遍歷的節點值。例如給定二叉樹返回其層次遍歷結果題解我們數據結構的書上教的層序遍歷就是利用一個隊列不斷的把左子樹和右子樹入隊。 題目 給定一個二叉樹,返回其按層次遍歷的節點值。 (即逐層地,從左到右訪問所有節點)。 例如:給定二叉樹: [3,9,20,null,null,15,7], 3 / 9 20 / 15 ...
閱讀 3018·2023-04-25 20:22
閱讀 3335·2019-08-30 11:14
閱讀 2590·2019-08-29 13:03
閱讀 3178·2019-08-26 13:47
閱讀 3218·2019-08-26 10:22
閱讀 1263·2019-08-23 18:26
閱讀 609·2019-08-23 17:16
閱讀 1908·2019-08-23 17:01