树必刷题第二部分

枫长...大约 19 分钟

112. 路径总和open in new window

98. 验证二叉搜索树open in new window

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路

通过递归遍历二叉树的每一个节点，并在遍历的过程中对于每个节点检查该节点的值是否在左子树的最大值和右子树的最小值之间。如果所有的节点都满足这个条件，则返回true，否则返回false。

在递归的过程中，它可以利用每个节点的值来更新最大值和最小值的限制，并在遍历该节点的左右子树时将这些限制传递下去。

因此，如果某个节点的值不在左子树的最大值和右子树的最小值之间，则该二叉树不是有效的BST。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return traverse(root, nullptr, nullptr);
    }

    bool traverse(TreeNode* root, TreeNode* min, TreeNode* max) {
        if(root == nullptr) {
            return true;
        }
        if(min != nullptr && root->val <= min->val) {
            return false;
        }
        if(max != nullptr && root->val >= max->val) {
            return false;
        }
        return traverse(root->right, root, max) && traverse(root->left, min, root);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return traverse(root, null, null);
    }
    
    public boolean traverse(TreeNode root, TreeNode min, TreeNode max) {
        if(root == null) {
            return true;
        }
        if(min != null && root.val <= min.val) {
            return false;
        }
        if(max != null && root.val >= max.val) {
            return false;
        }
        return traverse(root.right, root, max) && traverse(root.left, min, root);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return traverse(root,nil,nil)
}
func traverse(root,min,max *TreeNode)bool{
    if root==nil{
        return true
    }
    if min!=nil&&root.Val<=min.Val{
        return false
    }
    if max!=nil&&root.Val>=max.Val{
        return false
    }
    return traverse(root.Right,root,max)&&traverse(root.Left,min,root)
}

剑指 Offer 54. 二叉搜索树的第k大节点open in new window

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

解题思路

二叉搜索树的中序遍历可以得到数组从小到大的排序，想要从大到小可以对二叉搜索树进行反向中序遍历（先遍历右子树，再遍历根节点，最后遍历左子树），并使用栈来实现迭代过程。具体步骤如下：

初始化一个栈 st 和一个指针 cur 指向根节点 root，初始化计数器 cnt 为0。
使用 while 循环进行遍历，当栈非空或者 cur 不为空时进行迭代。
如果 cur 不为空，将当前节点 cur 压入栈中，然后将 cur 指向其右子节点。这样可以确保先遍历右子树。
如果 cur 为空，表示已经遍历到最右侧的节点，从栈顶取出一个节点，更新 cur 为该节点。接着将计数器 cnt 加1，判断当前遍历到的节点是否为第 k 大的节点。如果是，则返回当前节点的值。
最后，将 cur 指向其左子节点，继续遍历左子树。
若遍历结束还未找到第 k 大的元素，返回 -1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        while (root || !st.empty()) {
            while (root) {
                st.push(root);
                root = root->right;
            }
            root = st.top();
            st.pop();
            if (--k == 0) {
                return root->val;
            }
            root = root->left;
        }
        return -1;
    }
};

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> st = new Stack<>();
        while (root != null || !st.empty()) {
            while (root != null) {
                st.push(root);
                root = root.right;
            }
            root = st.pop();
            if (--k == 0) {
                return root.val;
            }
            root = root.left;
        }
        return -1;
    }
}

func kthLargest(root *TreeNode, k int) int {
    st := []*TreeNode{}
    for root != nil || len(st) > 0 {
        for root != nil {
            st = append(st, root)
            root = root.Right
        }
        root = st[len(st)-1]
        st = st[:len(st)-1]
        if k--; k == 0 {
            return root.Val
        }
        root = root.Left
    }
    return -1
}

230. 二叉搜索树中第K小的元素open in new window

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

解题思路

找第k小的方式就可以直接中序遍历找第k个遍历的元素，具体步骤如下：

首先，我们定义了一个成员变量 kG 和 ans，用于记录要找到的第 k 小的元素的值和答案。
然后，我们定义了一个递归函数 dfs，用于遍历二叉搜索树。dfs 函数的参数包括当前节点 root 和计数器 count。count 用于记录当前访问的是第几个元素。
在 dfs 函数中，我们先递归遍历当前节点的左子树，这样可以保证左子树中的元素都小于当前节点。
然后，如果 count 的值等于 kG，说明当前节点是第 k 小的元素，将其赋值给 ans，并直接返回即可。
否则，将计数器 count 的值加 1，表示已经访问了一个节点。
接下来，递归遍历当前节点的右子树，这样可以保证右子树中的元素都大于当前节点。
最后，在 kthSmallest 函数中，我们将 kG 的值赋为 k，计数器 count 的值赋为 0，然后调用 dfs 函数遍历整个二叉搜索树。
遍历完整个二叉搜索树之后，ans 变量中存储的就是第 k 小的元素的值，将其返回即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int kG;
    int ans;
    void dfs(TreeNode* root, int& count) {
        if (root == nullptr) {
            return;
        }
        dfs(root->left, count);
        if (++count == kG) {
            ans = root->val;
            return;
        }
        dfs(root->right, count);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        kG = k;
        int count = 0;
        dfs(root, count);
        return ans;
    }
};

class Solution {
    private int kG;
    private int ans;

    private void dfs(TreeNode root, int[] count) {
        if (root == null) {
            return;
        }
        dfs(root.left, count);
        if (++count[0] == kG) {
            ans = root.val;
            return;
        }
        dfs(root.right, count);
    }

    public int kthSmallest(TreeNode root, int k) {
        kG = k;
        int[] count = new int[1];
        dfs(root, count);
        return ans;
    }
}

func kthSmallest(root *TreeNode, k int) int {
    kG := k
    count := []int{0}
    var ans int

    var dfs func(*TreeNode, []int)
    dfs = func(root *TreeNode, count []int) {
        if root == nil {
            return
        }
        dfs(root.Left, count)
        if count[0]++; count[0] == kG {
            ans = root.Val
            return
        }
        dfs(root.Right, count)
    }

    dfs(root, count)
    return ans
}

450. 删除二叉搜索树中的节点open in new window

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

解题思路

BST的特点是左子树中所有的节点一定小于当前节点，右子树的所有节点一定大于当前节点。删除节点用递归比较方便，具体操作如下：

首先，我们判断根节点是否为空，如果为空则直接返回 null。
接下来，我们判断根节点的值是否等于要删除的值 key。如果相等，分三种情况讨论：
- 如果根节点的左子树为空，直接返回右子树，因为右子树中的节点都比根节点大。
- 如果根节点的右子树为空，直接返回左子树，因为左子树中的节点都比根节点小。
- 如果根节点的左右子树都不为空，需要找到根节点右子树中的最小值节点 cur，将根节点的左子树连接到 cur 的左子树上，然后返回根节点的右子树。这个过程中，我们需要遍历右子树，直到找到最小值节点 cur。
如果根节点的值大于要删除的值 key，说明要删除的节点在根节点的左子树中，递归调用 deleteNode 函数，将根节点的左子树作为新的根节点继续删除。
如果根节点的值小于要删除的值 key，说明要删除的节点在根节点的右子树中，递归调用 deleteNode 函数，将根节点的右子树作为新的根节点继续删除。
最后，返回根节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return nullptr;
        }
        if (root->val == key) {
            if (!root->left) {
                return root->right;
            }
            if (!root->right) {
                return root->left;
            }
            TreeNode* cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            cur->left = root->left;
            return root->right;
        }
        if (root->val > key) {
            root->left = deleteNode(root->left, key);
        } else {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode cur = root.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            cur.left = root.left;
            return root.right;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == key {
        if root.Left == nil {
            return root.Right
        }
        if root.Right == nil {
            return root.Left
        }
        cur := root.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        cur.Left = root.Left
        return root.Right
    }
    if root.Val > key {
        root.Left = deleteNode(root.Left, key)
    } else {
        root.Right = deleteNode(root.Right, key)
    }
    return root
}

958. 二叉树的完全性检验open in new window

给定一个二叉树的 root ，确定它是否是一个完全二叉树。
在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

解题思路

思路是利用层序遍历（BFS）来判断一棵二叉树是否是完全二叉树。具体来说，首先将根节点加入队列中。然后从队列中依次取出节点进行处理。对于每个节点，分以下三种情况：

如果 prev 为 nullptr 且当前节点不为 nullptr，说明遇到了一个非完全二叉树，直接返回 false。
如果当前节点不为 nullptr，将其左右子节点加入队列中。
更新 prev 为当前节点。

其中 prev 是记录上一个节点，用来判断当前节点是否是完全二叉树的。如果在某个节点上出现了左子树为空但右子树不为空的情况，那么 prev 就会是 nullptr，下一个非空节点出现时，说明这棵树不是完全二叉树，直接返回 false。

最后，如果所有节点都处理完了，那么这棵树就是完全二叉树，返回 true 即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        queue<TreeNode*> q;
        TreeNode* prev = root;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (prev == nullptr && node != nullptr) {
                return false;
            }
            if (node != nullptr) {
                q.push(node->left);
                q.push(node->right);
            }
            prev = node;
        }
        return true;
    }
};

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode prev = root;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            if (prev == null && node != null)
                return false;
            if (node != null) {
                queue.add(node.left);
                queue.add(node.right);
            }
            prev = node;
        }
        return true;
    }
}

func isCompleteTree(root *TreeNode) bool {
    if root == nil {
        return true
    }
    q := []*TreeNode{root}
    var prev *TreeNode = root
    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        if prev == nil && node != nil {
            return false
        }
        if node != nil {
            q = append(q, node.Left)
            q = append(q, node.Right)
        }
        prev = node
    }
    return true
}

剑指 Offer 26. 树的子结构open in new window

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构，即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:
3
/ \
4   5
/ \
1   2
给定的树 B：
4 
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

解题思路

这道题就是递归的去比较每一颗子树具不具备相应的子结构，以下是具体操作：

定义一个辅助函数 check，它接受两个参数：二叉树 A 的节点和二叉树 B 的节点。这个函数会递归地比较两棵树的结构和节点值是否匹配。
在 check 函数中：
a. 如果二叉树 B 的节点为空，说明 B 已经匹配完毕，返回 true。
b. 如果二叉树 A 的节点为空，或者 A 和 B 的节点值不匹配，返回 false。
c. 递归地比较 A 和 B 的左子树和右子树，返回它们的匹配结果。
在 isSubStructure 函数中：
a. 如果二叉树 A 或 B 为空，返回 false，因为非空的树 B 不能是空树 A 的子结构。
b. 首先尝试用 check 函数比较 A 和 B 的根节点。如果根节点匹配，则返回 true。
c. 如果根节点不匹配，则递归地检查 A 的左子树和右子树是否包含 B，返回递归结果的逻辑或。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* A,TreeNode* B){
        if(B==nullptr) return true;     //B已经消耗完了
        if(A==nullptr || A->val!=B->val) return false;      //如果B还没消耗完但是A已经没了，或者根本匹配不上
        return check(A->left,B->left) && check(A->right,B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(B==nullptr || A==nullptr) return false;
        return check(A,B)|| isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

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

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return check(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
}

func check(A *TreeNode, B *TreeNode) bool {
    if B == nil {
        return true
    }
    if A == nil || A.Val != B.Val {
        return false
    }
    return check(A.Left, B.Left) && check(A.Right, B.Right)
}

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }
    return check(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

113.路径总和 IIopen in new window

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

解题思路

采用深度优先搜索来遍历所有的从根节点到叶子节点的路径，当路径上的节点和等于给定值 targetSum 时，将路径加入到结果中。

具体实现时，定义一个 dfs 函数来进行深度优先搜索，函数参数包括当前节点 root、当前路径和 sum、目标和 targetSum，以及已经走过的节点 tmp。在遍历到叶子节点时，判断路径和是否等于目标和，如果是则将路径加入到结果中。在搜索过程中，需要使用 tmp 数组来记录已经走过的节点。

为了方便存储结果，定义一个二维数组 ans 来存储所有符合条件的路径。

在 pathSum 函数中，定义一个空的 tmp 数组，然后调用 dfs 函数进行搜索。最后返回 ans 数组作为结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;

    void dfs(vector<int>& tmp, TreeNode* root, int sum, int targetSum) {
        if (!root) {
            return;
        }
        tmp.emplace_back(root->val);
        sum += root->val;
        if (!root->left && !root->right && sum == targetSum) {
            ans.emplace_back(tmp);
        }
        dfs(tmp, root->left, sum, targetSum);
        dfs(tmp, root->right, sum, targetSum);
        tmp.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> tmp;
        dfs(tmp, root, 0, targetSum);
        return ans;
    }
};

class Solution {
    List<List<Integer>> ans = new ArrayList<>();

    public void dfs(List<Integer> tmp, TreeNode root, int sum, int targetSum) {
        if (root == null) {
            return;
        }
        tmp.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null && sum == targetSum) {
            ans.add(new ArrayList<>(tmp));
        }
        dfs(tmp, root.left, sum, targetSum);
        dfs(tmp, root.right, sum, targetSum);
        tmp.remove(tmp.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> tmp = new ArrayList<>();
        dfs(tmp, root, 0, targetSum);
        return ans;
    }
}

func dfs(ans *[][]int, tmp *[]int, root *TreeNode, sum, targetSum int) {
    if root == nil {
        return
    }
    *tmp = append(*tmp, root.Val)
    sum += root.Val
    if root.Left == nil && root.Right == nil && sum == targetSum {
        *ans = append(*ans, append([]int{}, *tmp...))
    }
    dfs(ans, tmp, root.Left, sum, targetSum)
    dfs(ans, tmp, root.Right, sum, targetSum)
    *tmp = (*tmp)[:len(*tmp)-1]
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    ans := [][]int{}
    tmp := []int{}
    dfs(&ans, &tmp, root, 0, targetSum)
    return ans
}

103. 二叉树的锯齿形层序遍历open in new window

给你二叉树的根节点root，返回其节点值的锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

解题思路

层序遍历的一个变化考法，首先层序遍历属于常考题目，这个板子必须要记住。正常的层序遍历时的队列是队尾进，队头出；锯齿形就先队尾进，队头出，然后再队头进，队尾出，每遍历一层就切换一次。具体操作如下：

定义一个双端队列 q 来存储二叉树的节点，初始时将根节点 root 压入队列。
定义一个向量 ans 来存储结果，以及一个临时向量 t 用于存储每一层的节点值。
定义一个标志位 flag，初始值为 1。当 flag 为 1 时，表示从左到右遍历；当 flag 为 0 时，表示从右到左遍历。
当队列不为空时，执行以下操作：
a. 计算当前队列的大小 sz，表示这一层有多少个节点。
b. 遍历这一层的所有节点：
i. 如果 flag 为 1，则从队列头部取出节点，将节点值存入临时向量 t，然后将该节点的左右子节点从左到右依次压入队列尾部。
ii. 如果 flag 为 0，则从队列尾部取出节点，将节点值存入临时向量 t，然后将该节点的右左子节点从右到左依次压入队列头部。
c. 将临时向量 t 添加到结果向量 ans，并清空临时向量 t。
d. 反转标志位 flag。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) {
            return ans;
        }
        deque<TreeNode*> q = {root};
        int flag = 1;
        while (!q.empty()) {
            vector<int> t;
            int sz = q.size();
            while (sz--) {
                TreeNode* cur = flag ? q.front() : q.back();
                if (flag) {
                    q.pop_front();
                } else {
                    q.pop_back();
                }
                t.emplace_back(cur->val);
                if (flag) {
                    if (cur->left) {
                        q.emplace_back(cur->left);
                    }
                    if (cur->right) {
                        q.emplace_back(cur->right);
                    }
                } else {
                    if (cur->right) {
                        q.emplace_front(cur->right);
                    }
                    if (cur->left) {
                        q.emplace_front(cur->left);
                    }
                }
            }
            flag = !flag;
            ans.emplace_back(t);
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean flag = true;
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> t = new ArrayList<>();
            while (sz-- > 0) {
                TreeNode cur = flag ? q.pollFirst() : q.pollLast();
                t.add(cur.val);
                if (flag) {
                    if (cur.left != null) {
                        q.offerLast(cur.left);
                    }
                    if (cur.right != null) {
                        q.offerLast(cur.right);
                    }
                } else {
                    if (cur.right != null) {
                        q.offerFirst(cur.right);
                    }
                    if (cur.left != null) {
                        q.offerFirst(cur.left);
                    }
                }
            }
            flag = !flag;
            ans.add(t);
        }
        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    
    flag := true
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        cur := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            cur = append(cur, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        if !flag {
            reverse(cur)
        }
        flag = !flag
        res = append(res, cur)
    }

    return res
}

func reverse(arr []int) {
    l, r := 0, len(arr)-1
    for l < r {
        arr[l], arr[r] = arr[r], arr[l]
        l++
        r--
    }
}

199. 二叉树的右视图open in new window

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路

层序遍历的变化题目，每次遍历只要记录每一层的最右节点即可。以下是具体操作：

定义一个队列 q 来存储二叉树的节点，初始时将根节点 root 压入队列。
定义一个 cur 指针指向当前处理的节点，初始值为 root。
定义一个vector ans 来存储结果。
检查根节点是否为空，如果为空，则返回 ans。
当队列不为空时，执行以下操作：
a. 计算当前队列的大小 sz，表示这一层有多少个节点。
b. 定义一个变量 tmp，用于记录当前层最右侧的节点值，初始值为 101（题目中节点值的范围为 [0,100]）。
c. 遍历这一层的所有节点：
i. 从队列头部取出节点，更新当前节点指针 cur。
ii. 更新 tmp 的值为当前节点的值。
iii. 如果当前节点的左子节点不为空，将左子节点压入队列。
iv. 如果当前节点的右子节点不为空，将右子节点压入队列。
d. 如果 tmp 不等于 101，则将 tmp 值添加到结果向量 ans 中。
返回结果 ans。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        deque<TreeNode*> q = {root};
        vector<int> ans;
        if (root == nullptr) {
            return ans;
        }
        while (!q.empty()) {
            int sz = q.size();
            int rightMost = 0;
            for (int i = 0; i < sz; i++) {
                TreeNode* cur = q.front();
                q.pop_front();
                rightMost = cur->val;
                if (cur->left != nullptr) {
                    q.emplace_back(cur->left);
                }
                if (cur->right != nullptr) {
                    q.emplace_back(cur->right);
                }
            }
            ans.emplace_back(rightMost);
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        while (!q.isEmpty()) {
            int sz = q.size();
            int rightMost = 0;
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                rightMost = cur.val;
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            ans.add(rightMost);
        }
        return ans;
    }
}

type deque struct {
    list []interface{}
}

func NewDeque() *deque {
    return &deque{}
}

func (d *deque) PushFront(v interface{}) {
    d.list = append([]interface{}{v}, d.list...)
}

func (d *deque) PushBack(v interface{}) {
    d.list = append(d.list, v)
}

func (d *deque) PopFront() interface{} {
    if len(d.list) == 0 {
        return nil
    }
    v := d.list[0]
    d.list = d.list[1:]
    return v
}

func (d *deque) PopBack() interface{} {
    if len(d.list) == 0 {
        return nil
    }
    v := d.list[len(d.list)-1]
    d.list = d.list[:len(d.list)-1]
    return v
}

func (d *deque) Len() int {
    return len(d.list)
}

func (d *deque) Empty() bool {
    return len(d.list) == 0
}

func rightSideView(root *TreeNode) []int {
    q := NewDeque()
    q.PushBack(root)
    ans := []int{}
    if root == nil {
        return ans
    }
    for !q.Empty() {
        sz := q.Len()
        rightMost := 0
        for i := 0; i < sz; i++ {
            cur := q.PopFront().(*TreeNode)
            rightMost = cur.Val
            if cur.Left != nil {
                q.PushBack(cur.Left)
            }
            if cur.Right != nil {
                q.PushBack(cur.Right)
            }
        }
        ans = append(ans, rightMost)
    }
    return ans
}

你认为这篇文章怎么样？

昵称

邮箱

按正序
按倒序
按热度

树必刷题第二部分

预览: